資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中所有相鄰元素都滿足其中一個能被另一個整除的陣列的計數
給定兩個名為“one”和“another”的整數。目標是找到可能的陣列數量，使得：
陣列中的元素在 1 到“another”的範圍內。
陣列的所有元素都滿足 arr[i] 能被 arr[i+1] 整除或 arr[i+1] 能被 arr[i+2] 整除……以此類推。
陣列的長度為“one”。
例如
輸入
one = 3, another = 2
輸出
Count of arrays in which all adjacent elements are such that one of them divide the another are: 8
解釋
The arrays will be: [ 1,1,1 ], [ 1,1,2 ], [ 1,2,1 ], [ 1,2,2 ], [ 2,1,1 ], [ 2,1,2 ], [ 2,2,1 ], [ 2,2,2 ]
輸入
one = 2, another = 3
輸出
Count of arrays in which all adjacent elements are such that one of them divide the another are: 7
解釋
The arrays will be: [ 1,1 ], [ 2,2 ], [ 3,3 ], [ 1,2 ], [ 1,3 ], [ 2,2 ], [ 3,3 ]
**下面程式中使用的方案如下：**
我們知道每個陣列的第一個元素可以是 [1,another] 範圍內的任何數字。下一個元素將始終是前一個元素的倍數或因子，以使可整除條件成立。此外，因子或倍數應該小於“another”。我們將使用動態規劃來儲存計算結果。為此，我們使用陣列 arr[][]。arr[1][another] 將為 1，因為它們將是單個元素陣列。arr[i][j]=arr[i−1][j]+前一個元素的因子+前一個元素的倍數（小於 another）。
將整數 one 和 another 作為輸入。
函式 adjacent_elements(int first, int second) 返回所有相鄰元素都滿足其中一個能被另一個整除的陣列的數量。
將初始計數設定為 0，並建立陣列 arr[size][size]。
使用 memset 將所有計數初始化為 0。
建立兩個向量：vec 用於儲存因子，vec_2 用於儲存倍數。
使用兩個 for 迴圈從 i=t 到 i=second 和 j=2*i 到 j=second 進行遍歷。將 j 的增量設定為 i。
將 i 新增到 vec[j] 中，並將 j 新增到 vec_2[i] 中。在 j 迴圈結束後，也將 i 新增到 vec[i] 中。
使用 for 迴圈設定 arr[1][i]。
再次遍歷陣列，現在遍歷 vec 和 vec_2，並將因子和倍數新增到 arr[i][j] 中。
最後，將所有 arr[first][i] 新增到計數中，並清除 vec[i] 和 vec_2[i]。
返回計數作為結果。
示例
#include <bits/stdc++.h>
using namespace std;
#define size 1000
int adjacent_elements(int first, int second){
int count = 0;
int arr[size][size];
memset(arr, 0, sizeof arr);
vector<int> vec[size], vec_2[size];
memset(vec, 0, sizeof vec);
memset(vec_2, 0, sizeof vec_2);
for (int i = 1; i <= second; i++){
for (int j = 2*i; j <= second; j += i){
vec[j].push_back(i);
vec_2[i].push_back(j);
}
vec[i].push_back(i);
}
for (int i = 1; i <= second; i++){
arr[1][i] = 1;
}
for (int i = 2; i <= first; i++){
for (int j = 1; j <= second; j++){
arr[i][j] = 0;
for (auto it: vec[j]){
arr[i][j] += arr[i−1][it];
}
for (auto it : vec_2[j]){
arr[i][j] += arr[i−1][it];
}
}
}
for (int i = 1; i <= second; i++){
count = count + arr[first][i];
vec[i].clear();
vec_2[i].clear();
}
return count;
}
int main(){
int one = 2, another = 2;
cout<<"Count of arrays in which all adjacent elements are such that one of them divide the another are: "<<adjacent_elements(one, another);
return 0;
}輸出
如果我們執行以上程式碼，它將生成以下輸出：
Count of arrays in which all adjacent elements are such that one of them divide the another are: 4
361 次瀏覽
