1022:角谷猜想
查看提交统计提问
总时间限制: 1000ms 内存限制: 65536kB
描述
所谓角谷猜想，是指对于任意一个正整数，如果是奇数，则乘3加1，如果是偶数，则除以2，得到的结果再按照上述规则重复处理，最终总能够得到1。如，假定初始整数为5，计算过程分别为16，8、4、2，1。
程序要求输入一个整数，将经过处理得到1的过程输出来。
输入
一个正整数N(N <= 2,000,000)
输出
从输入整数到1的步骤，每一步为一行，每一部中描述计算过程。最后一行输出"End"。如果输入为1，直接输出"End"。
样例输入
5
样例输出
5*3+1=16
16/2=8
8/2=4
4/2=2
2/2=1
End
#include<bits/stdc++.h>
using namespace std;
int main()
{
int N;
cin>>N;
while(N!=1)
{
if(N%2==0)
{
cout<<N<<"/2="<<N/2<<endl;
N=N/2;
}
else
{
if(N%2==1)
{
cout<<N<<"*3+1="<<N*3+1<<endl;
N=N*3+1;
}
}
}
while(N==1)
{
cout<<"End"<<endl; break;
}
return 0;
}
为超过时限
1.一个数字，非偶即奇。因此在else时，直接执行操作就好了。不用再判断
2.因为N <= 2,000,000，所以要用longlong
3.最后那个while根本没必要，直接输出“End”不就行了？
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long N;
cin>>N;
while(N!=1)
{
if(N%2==0)
{
cout<<N<<"/2="<<N/2<<endl;
N=N/2;
}
else
{
cout<<N<<"*3+1="<<N*3+1<<endl;
N=N*3+1;
}
}
cout<<"End"<<endl;
return 0;
}
试试
while(N>1)
{
if(N%2==1)
{
cout<<N<<"*3+1="<<N*3+1<<endl;
N=N*3+1;
}
while(N%2==0)
{
cout<<N<<"/2="<<N/2<<endl;
N=N/2;
}
}
cout<<"End"<<endl;
【以下回答由 GPT 生成】
根据角谷猜想，对于任意一个正整数N，通过以下规则进行计算，最终都会得到1：
现在的问题是，如何优化给出的代码以避免超过时间限制。我们可以采取以下几个步骤进行优化：
移除无用的条件判断和循环：代码中有一个无效的循环while(N==1)和其对应的条件判断if(N%2==1)，这段代码会一直执行，直到N不等于1，然后跳出循环。这是一个多余的循环，可以直接在第一个循环中判断N是否为1，如果是则输出"End"并退出循环。
使用位运算代替取余运算和除法运算：在判断N是否为偶数时，可以使用位运算N & 1来替代取余运算N%2。在将N除以2时，可以使用右移一位运算N >> 1来替代除法运算N/2。这样可以提高代码的执行效率。
以下是优化后的代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int N;
cin >> N;
while(N!=1)
{
if(N & 1) // 判断N是否为奇数
{
cout << N << "*3+1=" << N*3+1 << endl;
N = N*3+1;
}
else
{
cout << N << " /2=" << (N >> 1) << endl;
N >>= 1; // 将N右移一位
}
}
cout << "End" << endl;
return 0;
}
这样优化后的代码能够更高效地执行，并且避免超过时间限制。
【相关推荐】