資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用 C++ 統計給定字串的公因數個數
給定兩個字串 numo 和 demo 作為輸入。目標是找到這兩個字串的公因數個數。字串的因數使用以下技術找到：如果字串 str 有 sub1 作為其因數，那麼我們可以透過重複 sub1 任意次數來構建 str，直到生成 str。例如：str=abcabcabc sub1=abc
例如
輸入
numo = "abababab" demo = "abababababababab"
輸出
Count of number of common divisors of the given strings are: 2
解釋
The strings can be generated using following divisor substrings : “ab”, “abab”
輸入
numo = "pqqppqqp" demo = "pqpq"
輸出
Count of number of common divisors of the given strings are: 0
解釋
The strings do not have any common divisor. Only divisors of both are: “pqqp” for numo and “pq” for demo.
下面程式中使用的演算法如下 −
對於任何字串 sub1 成為 str 的因數，它必須是 str 的字首，並且其長度必須完全整除 str 的長度。使用這兩個字串 numo 和 demo 檢查 sub1 的這個條件，並相應地遞增計數。
將字串 numo 和 demo 作為輸入。
函式 verify(string str, int val) 獲取字串 str 並返回 1，如果從 0 到 val 的子字串可以重複生成 str。
函式 common_divisor(string numo, string demo) 獲取這兩個字串並返回給定字串的公因數個數。
將初始計數設定為 0。
計算輸入字串的長度。並將最小長度儲存在 min_val 中。
使用 for 迴圈從索引 i=0 遍歷到 min_val。
如果子字串的當前長度 i 整除 numo_size 和 demo_size 的長度，並且字首也匹配 numo.substr(0, i) == demo.substr(0, i)。
然後使用 verify() 查詢子字串 0 到 i 是否是 numo 和 demo 的因數。
如果 verify(numo,i) 和 verify(demo,i) 都返回 1，則遞增計數。
在 for 迴圈結束時返回計數作為結果。
示例
#include <bits/stdc++.h>
using namespace std;
int verify(string str, int val){
int length = str.length();
for (int i = 0; i < length; i++){
if(str[i] != str[i % val]){
return 0;
}
}
return 1;
}
int common_divisor(string numo, string demo){
int count = 0;
int numo_size = numo.size();
int demo_size = demo.size();
int min_val = min(numo_size, demo_size);
for(int i = 1; i <= min_val; i++){
if(numo_size % i == 0){
if(demo_size % i == 0){
if(numo.substr(0, i) == demo.substr(0, i)){
if(verify(numo, i)==1){
if(verify(demo, i)==1){
count++;
}
}
}
}
}
}
return count;
}
int main(){
string numo = "abababab";
string demo = "abababababababab";
cout<<"Count the number of common divisors of the given strings are:
"<<common_divisor(numo, demo);
return 0;
}輸出
如果我們執行上述程式碼，它將生成以下輸出：
Count the number of common divisors of the given strings are: 3
更新於: 2021年1月5日
224 次檢視
廣告