欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

C语言程序设计100例之(3): Cantor表

程序员文章站 2022-05-21 14:48:47
例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项,因此有:

                    C语言程序设计100例之(3): Cantor表

        可以用一个循环计算第n项所在的行数,如下:

                  for (i=1; i*(i+1)/2<n; i++) ;

        循环退出后,i*(i+1)/2刚好大于或等于n,因此,i就是第n项所在的行。

        第n项在第i行中属于第几项又可以计算出来,公式为:

           C语言程序设计100例之(3): Cantor表        即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天,因此有:   

                C语言程序设计100例之(3): Cantor表 

        可以用一个循环计算第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滴盐水,因此有:

                C语言程序设计100例之(3): Cantor表

        可以用一个循环计算滴玩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;

}