例57 3n+1問題
問題描述
考慮如下的序列生成演算法：從整數 n 開始，如果 n 是偶數，把它除以 2；如果 n 是奇數，把它乘 3 加1，用新得到的值重復上述步驟，直到 n = 1 時停止，例如，n = 22 時該演算法生成的序列是：22，11，34，17，52，26，13，40，20，10，5，16，8，4，2，1，
人們猜想（沒有得到證明）對于任意整數 n，該演算法總能終止于 n = 1，這個猜想對于至少 1000 000內的整數都是正確的，
對于給定的 n，該序列的元素（包括 1）個數被稱為 n 的回圈節長度，在上述例子中，22 的回圈節長度為 16，
輸入兩個數 i 和 j，你的任務是計算 i 到 j（包含 i 和 j）之間的整數中，回圈節長度的最大值，
輸入格式
輸入每行包含兩個整數 i 和 j，所有整數大于 0，小于 1 000000，
輸出格式
對于每對整數 i 和 j，按原來的順序輸出 i 和 j，然后輸出二者之間的整數中的最大回圈節長度，這三個整數應該用單個空格隔開，且在同一行輸出，對于讀入的每一組資料，在輸出中應位于單獨的一行，
樣例輸入
1 10
100 200
201 210
900 1000
樣例輸出
1 10 20
100 200 125
201 210 89
900 1000 174
（1）編程思路，
計算給定區間中每個數的回圈節長度，用max保存這些數的回圈節長度的最大值，
定義陣列int cache[1000000]={0}，其中cache[i]保存整數i的回圈節長度，在計算程序中采用填表的方法保存已有計算結果，可以顯著減少計算時間，例如，若已計算出5的回圈節長度為6（cache[5]=6），則10的回圈節長度為cache[10]=cache[5]+1，
另外，在中間計算程序可能會超過 int（4位元組存盤空間） 型資料所能表示數的范圍，故采用long long （8 位元組存盤空間）型整數來運算，
（2）源程式，
#include <stdio.h>
#define MAXSIZE 1000000
int cache[MAXSIZE]={0};
int counter(long long number)
{
if (number == 1)
return 1;
if (number%2==1)
number=3*number+1;
else
number/=2;
if (number < MAXSIZE )
{
if (!cache[number])
cache[number] = counter(number);
return 1 + cache[number];
}
return 1 + counter(number);
}
int main()
{
int begin,end;
while (scanf("%d%d",&begin,&end)!=EOF)
{
int max=0,t;
int left=begin<end?begin:end;
int right=begin>end?begin:end;
for (int k = left; k <= right; k++)
{
t=counter(k);
if (t>max) max=t;
}
printf("%d %d %d\n",begin,end,max);
}
return 0;
}
習題57
57-1 角谷步數
問題描述
你聽說過角谷猜想嗎？
任意的正整數，比如 5， 我們從它開始，如下規則計算：
如果是偶數，則除以2，如果是奇數，則乘以3再加1，
如此回圈，最終必會得到“1” !
比如 5 的處理程序是：5 ---> 16 ---> 8 ---> 4 ---> 2 ---> 1，
一個正整數經過多少步才能變成1， 稱為角谷步數，
對于5而言，步數也是5；對于1，步數為0，
撰寫程式，對于輸入的整數n，求角谷步數為n的最小的正整數，
輸入
輸入包括多行，每行包含一個整數N（1<=N<=300），
輸出
對于輸入的每個整數N，輸出一行，包含一個整數，表示第N個幸運數字，
輸入樣例
3
4
7
輸出樣例
8
16
3
（1）編程思路，
同例57一樣，定義陣列int cache[1000000]={0}，其中cache[i]保存整數i的回圈節長度，cache[i]-1的值就是整數i的角谷步數，
要求角谷步數為n的最小的正整數，從1開始搜索，若某個數i的cache[i]==n+1，則i就是所求的最小整數，
（2）源程式，
#include <stdio.h>
#define MAXSIZE 1000000
int cache[MAXSIZE]={0};
int counter(long long number)
{
if (number == 1)
return 1;
if (number%2==1)
number=3*number+1;
else
number/=2;
if (number < MAXSIZE )
{
if (!cache[number])
cache[number] = counter(number);
return 1 + cache[number];
}
return 1 + counter(number);
}
int main()
{
int n;
while (scanf("%d",&n)!=EOF)
{
int i,t;
for (i=1; ; i++)
{
t=counter(i);
if (t==n+1) break;
}
printf("%d\n",i);
}
return 0;
}
57-2 Good Numbers
問題描述
一個數N，如果它每一個位數字之和可以整除10，那么它就是Good Numbers，比如451就是一個Good Numbers，4+5+1=10，求[A,B]之間這樣的數的個數，
輸入
輸入第1行包含一個整數T (T <= 10000) ，表示測驗用例的組數；
之后有T行，每行兩個整數A和B（0 <= A <= B <= 1018），
輸出
對于每個測驗用例，輸出資訊為“Case #X:P”，其中X表示第X組測驗用例（X從1開始）,P表示[A,B]之間Good Numbers的個數，
輸入樣例
2
1 10
1 20
輸出樣例
Case #1: 0
Case #2: 1
（1）編程思路，
先列出前20個Good Numbers為：0，19，28，37，46，55，64，73，82，91，109，118，127，136，145，154，163，172，181，190……，由此可以發現：
[0,10]之間Good Numbers的個數為1
[0,100]之間Good Numbers的個數為10
[0,1000]之間Good Numbers的個數為100
[0,990]之間Good Numbers的個數為99
[0,992]之間Good Numbers的個數為100
……
[0,n]之間Good Numbers的個數為n/10 + (1或0)，其中加1的情況為：n/10*10 到n有1個Good Numbers，例如：n=997，則Good Numbers的個數99 +1，因為990到997之間的992就是一個Good Numbers，
（2）源程式，
#include <stdio.h>
int isOne(long long n) // 例如：997計算990-997之間有沒有符合條件的數
{
int s=0;
for(long long i=n/10*10;i<=n;i++)
{
long long t=i;
s=0;
while (t)
{
s+=t%10;
t/=10;
}
if (s%10==0) return 1;
}
return 0;
}
long long getNum(long long n)
{
if (n<0) return 0;
if (n<=10) return 1;
return n/10+isOne(n);
}
int main()
{
int t,cas=1;
scanf("%d",&t);
while(t--)
{
long long a,b;
scanf("%lld%lld",&a,&b);
printf("Case #%d: %lld\n",cas++,getNum(b)-getNum(a-1));
}
return 0;
}
57-3 Rabbit Number
問題描述
設 S(N ) 表示 N 的各位數字之和，如 S(484) = 4+8+4 = 16， S(22) = 2+2 = 4，如果一個正整數滿足 S(x*x) = S(x) *S(x)，我們稱之為 Rabbit N umber，比方說，22 就是一個 Rabbit Number，因為 S(484) = S(22) *S(22)，
現在，給出一個區間 [L, R]，求在該區間內的 Rabbit N umber 的個數，
輸入格式
輸入僅一行，為空格隔開的兩個數 L 和 R（1≤L≤R≤109），
輸出格式
輸出僅一行一個整數，表示所求 Rabbit N umber 的個數，
輸入樣例
1 58
輸出樣例
12
（1）編程思路，
首先，一個Rabbit Number的各位數字一定不超過3，
這個結論可簡單推出，設某數字x為1位，x>=4，因為x*x有進位，所以s(x*x)= x*x/10+x*x%10；而s(x)*s(x)=x*x，這樣，s(x*x)< <s(x)*s(x)，一定不是Rabbit Number，
既然各位數字不超過3，而區間中數字的位數不超過10位，這樣可以列舉每一位上的數字（0~3），對于列舉的每個數，若滿足在區間[L,R]中且為Rabbit N umber的要求，則進行計數，
（2）源程式，
#include <stdio.h>
int digitSum(long long x)
{
long long a=x;
int sum=0;
while (a)
{
sum+=a%10;
a/=10;
}
return sum;
}
int main()
{
long long l,r;
int ans=0;
int a[11],i;
scanf("%lld%lld",&l,&r);
int f=1;
for (a[1]=0;a[1]<=1 && f;a[1]++)
for (a[2]=0;a[2]<=3 && f;a[2]++)
for (a[3]=0;a[3]<=3 && f;a[3]++)
for (a[4]=0;a[4]<=3 && f;a[4]++)
for (a[5]=0;a[5]<=3 && f;a[5]++)
for (a[6]=0;a[6]<=3 && f;a[6]++)
for (a[7]=0;a[7]<=3 && f;a[7]++)
for (a[8]=0;a[8]<=3 && f;a[8]++)
for (a[9]=0;a[9]<=3 && f;a[9]++)
for (a[10]=0;a[10]<=3 && f;a[10]++)
{
long long num=0;
for (i=1;i<=10;i++)
{
num=num*10+a[i];
}
if (num>r)
{
f=0;
break;
}
if(num>=l&&num<=r)
{
if(digitSum(num)*digitSum(num)==digitSum(num*num)) ans++;
}
}
printf("%d\n",ans);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/421324.html
標籤：其他