例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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/63300.html
標籤：C
上一篇：C學習筆記(2)---各類函式