数据结构
网络
关系数据库管理系统
操作系统
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 次浏览
