例3 Cantor表 題目描述 現代數學的著名證明之一是Georg Cantor證明瞭有理數是可枚舉的。他是用下麵這一張表來證明這一命題的： 1/1 1/2 1/3 1/4 …… 2/1 2/2 2/3 …… 3/1 3/2 …… 4/1 …… …… 現以z字型方法給上表的每項編號。方法為：第一項是 ...
例3 Cantor表
題目描述
現代數學的著名證明之一是Georg Cantor證明瞭有理數是可枚舉的。他是用下麵這一張表來證明這一命題的：
1/1 1/2 1/3 1/4 ……
2/1 2/2 2/3 ……
3/1 3/2 ……
4/1 ……
……
現以z字型方法給上表的每項編號。方法為：第一項是1/1，然後是1/2、2/1、3/1、2/2、1/3、1/4、2/3……。
輸入格式
整數N（1≤N≤10000000）
輸出格式
表中的第N項
輸入樣例
7
輸出樣例
1/4
（1）編程思路1。
可以把上面的數表右轉45度，成一金字塔形狀，如下所示：
1/1
2/1 1/2
3/1 2/2 1/3
4/1 3/2 2/3 1/4
…… …… …… ……
該金字塔第1行有1個數，第2行有2個數，…，第i行有i個數。並且第i行上的i個分數的分子從i~1，分母從1~i，即第1個分數為i/1，最後一個分數為1/i。
為輸出數表中的第N項，先需計算這一項在第幾行。設第N項在x行，由於前x-1行共有1+2+3+…+（x-1）項，前x行有1+2+…+x項，因此有：
可以用一個迴圈計算第n項所在的行數，如下：
for (i=1； i*(i+1)/2<n； i++) ；
迴圈退出後，i*(i+1)/2剛好大於或等於n，因此，i就是第n項所在的行。
第n項在第i行中屬於第幾項又可以計算出來，公式為：
即n減去前i-1行中的全部項數。
由於是以z字型方法給數表的每項編號，因此當行號為奇數時，編號從左往右進行；當行號為偶數時，編號從右往左進行。
這樣，當i為奇數時，第i行的第k項為（i+1-k）/（k）；當i為偶數時，第i行的第k項為（k）/（i+1-k）。
（2）源程式1。
#include <stdio.h>
int main()
{
int i,k,n;
scanf("%d",&n);
for (i=1; i*(i+1)/2<n; i++) ;
k=n-(i*(i-1)/2);
if (i%2!=0)
printf("%d/%d\n",i+1-k,k);
else
printf("%d/%d\n",k,i+1-k);
return 0;
}
（3）編程思路2。
通過迴圈的方式直接模擬求出第N個數應該位於第row行第s列。
（4）源程式2。
#include <stdio.h>
int main()
{
int n,s,row;
scanf("%d",&n);
row=1;
s=1;
while (s<n)
{
row++;
s+=row;
}
s=n-(s-row);
if (row%2==1)
printf("%d/%d\n",(row-s)+1,s);
else
printf("%d/%d\n",s,(row-s)+1);
return 0;
}
習題3
3-1 金幣
本題選自洛谷題庫 （https://www.luogu.org/problem/P2669）
題目描述
國王將金幣作為工資，發放給忠誠的騎士。第一天，騎士收到一枚金幣；之後兩天（第二天和第三天），每天收到兩枚金幣；之後三天（第四、五、六天），每天收到三枚金幣；之後四天（第七、八、九、十天），每天收到四枚金幣……；這種工資發放模式會一直這樣延續下去：當連續N天每天收到N枚金幣後，騎士會在之後的連續N+1天里，每天收到N+1枚金幣。
請計算在前K天里，騎士一共獲得了多少金幣。
輸入格式
一個正整數K，表示發放金幣的天數。
輸出格式
一個正整數，即騎士收到的金幣數。
輸入樣例#1
6
輸出樣例#1
14
輸入樣例#2
1000
輸出樣例#2
29820
說明/提示
【輸入輸出樣例 1 說明】
騎士第一天收到一枚金幣；第二天和第三天，每天收到兩枚金幣；第四、五、六天，每天收到三枚金幣。因此一共收到 1+2+2+3+3+3=14 枚金幣。
（1）編程思路1。
為計算在前N天里，騎士一共獲得了多少金幣。需要確定第N天發幾枚金幣。設第N天發x枚金幣，由於發x-1枚金幣可發1+2+3+…+（x-1）天，發x枚金幣可發1+2+…+x天，因此有：
可以用一個迴圈計算第n天發的金幣數，如下：
for (i=1； i*(i+1)/2<n； i++) ；
迴圈退出後，i*(i+1)/2剛好大於或等於n，因此，i就是第n天發的金幣數。1~i-1枚金幣一定發滿了相應的天數，即每天1枚金幣發了1天，每天2枚金幣發了2天，…，每天i-1枚金幣發了i-1天，先用迴圈累積每天發1~i-1枚金幣共發了多少，再加上每天發i枚金幣發的數目即可得到答案。
（2）源程式1。
#include <stdio.h>
int main()
{
int n,m,k,s,i;
scanf("%d",&k);
for (n=1; n*(n+1)/2<k; n++);
n--;
m=(1+n)*n/2;
for (s=0,i=1;i<=n;i++)
s+=i*i;
if (k-m>0)
s+=(k-m)*(n+1);
printf("%d\n",s);
return 0;
}
（3）編程思路2。
直接模擬發金幣過程。用一個二重迴圈完成，外迴圈控制發的天數，迴圈體中用內迴圈控制k枚金幣連發k天。
（4）源程式2。
#include <stdio.h>
int main()
{
int n,k=1,i=1,j,sum=0;
scanf("%d",&n);
while(i<=n) // 一直迴圈下去，直到
{
for(j=1;j<=k;j++) // 連給k天
{
sum=sum+k; // 加上今天獲得的錢
i++; // 總天數增加
if(i>n)
{
break;
}
}
k++; // 連給天數增加
}
printf("%d\n",sum);
return 0;
}
3-2 鹽水的故事
Problem Description
掛鹽水的時候，如果滴起來有規律，先是滴一滴，停一下；然後滴二滴，停一下；再滴三滴，停一下...，現在有一個問題：這瓶鹽水一共有VUL毫升，每一滴是D毫升，每一滴的速度是一秒（假設最後一滴不到D毫升，則花費的時間也算一秒），停一下的時間也是一秒這瓶水什麼時候能掛完呢？
Input
輸入數據包含多個測試實例，每個實例占一行，由VUL和D組成，其中 0<D<VUL<5000。
Output
對於每組測試數據，請輸出掛完鹽水需要的時間，每個實例的輸出占一行。
Sample Input
10 1
Sample Output
13
（1）編程思路。
先計算vul毫升鹽水需要滴多少滴滴玩。顯然，滴數N=(int)(vul/d); ，若最後一滴不到d毫升，花費的時間也算一秒，因此要註意滴數達到精度的要求，可進行如下校正：
if (vul-N*d>0.00001) N++;
為計算掛完鹽水需要的時間，需要確定中間停頓的次數。設滴玩N滴鹽水需要滴x次，由於前x-1次可滴下1+2+3+…+（x-1）滴鹽水，前x次可滴下1+2+…+x滴鹽水，因此有：
可以用一個迴圈計算滴玩N滴鹽水需要的次數，如下：
for (i=1； i*(i+1)/2<n； i++) ；
迴圈退出後，i*(i+1)/2剛好大於或等於n，因此，i就是滴玩N滴鹽水需要的次數。每兩次之間會停頓，因此停頓時間為i-1秒，加上N滴用時N秒即得所求答案。
（2）源程式。
#include <stdio.h>
int main()
{
double vul,d;
int s,n;
while (scanf("%lf%lf",&vul,&d)!=EOF)
{
s=(int)(vul/d);
if (vul-s*d>0.00001) s++;
for (n=1; n*(n+1)/2<s; n++);
n--;
printf("%d\n",s+n);
}
return 0;
}
3-3 Peter的煙
題目描述
Peter 有n根煙，他每吸完一根煙就把煙蒂保存起來，k(k>1)個煙蒂可以換一個新的煙，那麼 Peter 最終能吸到多少根煙呢？
輸入格式
測試數據包含多組，每組測試數據一行包括兩個整數n,k(1<n,k≤108 )。
輸出格式
對於每組測試數據，輸出一行包括一個整數表示最終煙的根數。
輸入樣例
4 3
10 3
100 5
輸出樣例
5
14
124
（1）編程思路。
設變數sum代表Peter可抽煙的總根數，n代表煙蒂數，因為Peter有n根煙，因此初始時，sum=n（可抽n根煙），煙蒂數為n（n根煙產生n個煙蒂）。
之後不斷用煙蒂換煙抽，由於k個煙蒂換一根煙，因此不斷執行
sum =sum+ n/k; （n個煙蒂換抽n/k根煙）
n = n/k + n%k; （n/k根煙產生n/k個煙蒂，加上前面換煙後多餘的不足換1根煙的n%k個煙蒂為新的煙蒂數）
重覆這個過程直到剩下的煙蒂數不足以換根煙。
（2）源程式。
#include <stdio.h>
int main()
{
int n,k,sum;
while(scanf("%d%d",&n,&k)!=EOF)
{
sum = n;
while(n >= k)
{
sum += n/k;
n = n/k + n%k;
}
printf("%d\n",sum);
}
return 0;
}
