int i=1;while(i<n){int j=n;while(j>1){j=j/2;i=i*2;}}为什么外层的循环的次数是log2n
时间: 2024-06-13 13:06:45 浏览: 12
这段代码中,外层循环的初始值为1,每次循环i的值翻倍,直到i>=n为止。而内层循环的初始值为n,每次循环j的值减半,直到j<=1为止。因此,内层循环的执行次数为log2n,而外层循环的执行次数也是log2n,因为每次循环i的值翻倍,所以外层循环的执行次数与内层循环的执行次数相同,都是log2n。因此,整个代码的时间复杂度为O(log2n)。
相关问题
#include <iostream> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int N = 10; int n, m; int a[N]; int main() { cout << "请输入结点数:" << endl; while (cin >> n >> m) //输入图1、2的结点数 { if (m != n) { cout << "两图不同构!!!" << endl; continue; } //根据结点数n、m,动态生成两个二维数组来存图(使用邻接矩阵的方式) vector<int> w1(n + 1, 0); vector<vector<int> > g1(n + 1, w1); vector<int> w2(m + 1, 0); vector<vector<int> > g2(m + 1, w2); for (int i = 1; i <= n; i++) a[i] = i; //初始化a数组 for (int i = 1; i <= n; i++) //输入图1的邻接矩阵 for (int j = 1; j <= n; j++) cin >> g1[i][j]; for (int i = 1; i <= m; i++) //输入图2的邻接矩阵 for (int j = 1; j <= m; j++) cin >> g2[i][j]; //全排列 do { bool f = 0; int temp[N][N]; memset(temp, 0, sizeof temp); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { temp[i][j] = g1[a[i]][a[j]]; } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (temp[i][j] != g2[i][j]) { f = 1; break; } } if (f == 1) break; } if (f == 0) cout << "两图同构^-^" << endl; } while (next_permutation(a + 1, a + 1 + n)); cout << "两图不同构!!!" << endl; } return 0; }简化的完整代码
这是一个判断两个图是否同构的程序,输入两个图的邻接矩阵,通过枚举两个图的节点的排列顺序,判断它们是否同构。如果是同构的,则输出"两图同构^-^",否则输出"两图不同构!!!"。
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 10;
int n, m;
int a[N];
int main() {
cout << "请输入结点数:" << endl;
while (cin >> n >> m) { //输入图1、2的结点数
if (m != n) {
cout << "两图不同构!!!" << endl;
continue;
}
//根据结点数n、m,动态生成两个二维数组来存图(使用邻接矩阵的方式)
vector<int> w1(n + 1, 0);
vector<vector<int> > g1(n + 1, w1);
vector<int> w2(m + 1, 0);
vector<vector<int> > g2(m + 1, w2);
for (int i = 1; i <= n; i++) a[i] = i; //初始化a数组
for (int i = 1; i <= n; i++) //输入图1的邻接矩阵
for (int j = 1; j <= n; j++)
cin >> g1[i][j];
for (int i = 1; i <= m; i++) //输入图2的邻接矩阵
for (int j = 1; j <= m; j++)
cin >> g2[i][j];
//全排列
do {
bool f = 0;
int temp[N][N];
memset(temp, 0, sizeof temp);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
temp[i][j] = g1[a[i]][a[j]];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (temp[i][j] != g2[i][j]) {
f = 1;
break;
}
}
if (f == 1) break;
}
if (f == 0) cout << "两图同构^-^" << endl;
} while (next_permutation(a + 1, a + 1 + n));
cout << "两图不同构!!!" << endl;
}
return 0;
}
```
#include<bits/stdc++.h> using namespace std; int main() { int n,t; cin>>n; for(int i=0;i<n;i++) { int a; cin>>a; t=a*a; int p=0,q=0; while(a>0) { p++; a/=10; } for(int j=1;j<=a;j++) { int y=t*j; if((y%int(pow(10,p)))==a) { cout<<j<<" "<<t*j<<endl; q++; break; } } if(q==0) cout<<"No"<<endl; } return 0; }改错
这段代码存在多个问题:
1. 在第二个 for 循环中,循环条件应该是 `j<=a` 而不是 `j<=a`,因为 `a` 已经在上一个 while 循环中被除以了 10,所以 `a` 的值已经变化了。
2. 在第二个 for 循环中,应该在循环前将 `q` 的值初始化为 0,否则 `q` 的值可能会一直为 1,导致后面的判断失效。
3. 在计算 `y` 的时候,应该先将 `j` 和 `t` 相乘,再将结果赋值给 `y`,否则 `y` 的值一直为 0。
下面是修改后的代码:
```c++
#include<bits/stdc++.h>
using namespace std;
int main() {
int n,t;
cin>>n;
for(int i=0;i<n;i++)
{
int a;
cin>>a;
t=a*a;
int p=0,q=0;
while(a>0)
{
p++;
a/=10;
}
q=0; // 初始化 q 的值为 0
for(int j=1;j<=a;j++) // 修改循环条件
{
int y=j*t; // 修改计算 y 的方式,先将 j 和 t 相乘
if((y%int(pow(10,p)))==a)
{
cout<<j<<" "<<t*j<<endl;
q++;
break;
}
}
if(q==0)
cout<<"No"<<endl;
}
return 0;
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)