C趣味程序百例(23)

文章类别：C语言程序设计 | 发表日期:2008-9-24 14:44:44

71.约瑟夫问题
72.邮票组合
73 和数能表示1~23的5个正整数



71.约瑟夫问题
    这是17世纪的法国数学家加斯帕在《数目的游戏问题》中讲的一个故事：15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。
*问题分析与算法设计
    约瑟夫问题并不难，但求解的方法很多；题目的变化形式也很多。这里给出一种实现方法。
    题目中30个人围成一圈，因而启发我们用一个循环的链来表示。可以使用结构数组来构成一个循环链。结构中有两个成员，其一为指向下一个人的指针，以构成环形的链；其二为该 人是否被扔下海的标记，为1表示还在船上。从第一个人开始对还未扔下海的人进行计数，每数到9时，将结构中的标记改为0，表示该人已被扔下海了。这样循环计数直到有15个人被扔下海为止。
*程序与程序注释
#include<stdio.h>
struct node
{
    int nextp;            /*指向下一个人的指针(下一个人的数组下标)*/
    int no_out;       /*是否被扔下海的标记。1：没有被扔下海。0：已被扔下海*/
}link[31];            /*30个人，0号元素没有使用*/
void main()
{
    int i,j,k;
    printf("The original circle is(+:pagendom,@:christian):\n");
    for(i=1;i<=30;i++)         /*初始化结构数组*/
    {
        link[i].nextp=i+1;         /*指针指向下一个人(数组元素下标)*/
        link[i].no_out=1;        /*标志置为1，表示人都在船上*/
    }
    link[30].nextp=1;       /*第30个人的指针指向第一个人以构成环*/
    j=30;             /*j:指向已经处理完毕的数组元素，从link[i]指向的人开始计数*/
    for(i=0;i<15;i++)          /*i:已扔下海的人数计数器*/
    {
        for(k=0;;)          /*k:决定哪个人被扔下海的计数器*/
            if(k<15)
            {
                j=link[j].nextp;            /*修改指针，取下一个人*/
                k+=link[j].no_out;         /*进行计数。因已扔下海的人计标记为0*/
            }
            else break;              /*计数到15则停止计数*/
        link[j].no_out=0;        /*将标记置 0，表示该人已被扔下海*/
    }
    for(i=1;i<=30;i++)           /*输出结果*/
        printf("%c",link[i].no_out? '@':'+');    /*+:被扔下海， @：在船上*/
    printf("\n");
}
*运行结果
    The original circle is(+:pagandom, @:christian):
    +++@@+@+@@@+@+++@@+@@@+++@+@@+
    (+"表示被扔下海海的非教徒     @：留在船上活命的教徒)

*思考题
    有N个小孩围 成一圈并依次编号，教师指定从第M个小孩开始报数，报到第S个小孩即令其出列。然后从下一个孩子继续报数，数到第S个小孩又令其出列，如此直到所有的孩子都出列。求小孩出列的先后顺序。

----------------------------------------------------------------------

72.邮票组合
    某人有四张3分的邮票和三张5分的邮票，用这些邮票中的一张或若干张可以得到多少种不同的邮资？
*问题分析与算法设计 
    将问题进行数学分析，不同张数和面值的邮票组成的邮资可用下列公式计算：
            S=3*i+5*j
    其中i为3分邮柰的张数，j为5分的张数
    按题目的要求，3分的邮票可以取0、1、2、3、4张，5分的邮票可以取0、1、2、3张。采用穷举方法进行组合，可以求出这些不同面值不同张数的邮标组合后的邮资。
*程序与程序注释
#include<stdio.h>
int a[27];
void main()
{
    int i,j,k,s,n=0;
    for(i=0;i<=4;i++)           /*i:取三分邮票的张数*/
        for(j=0;j<=3;j++)       /*j:取5分邮票的张数*/
        {
            s=i*3+j*5;        /*计算组成的邮票面值*/
            for(k=0;a[k];k++)     /*查找是否有相同的邮资*/
                if(s==a[k])break;
            if(!a[k]&&s)         /*没有找到相同的邮资则满足要求存入数组*/
            {
                a[k]=s; n++;
            }
        }
    printf("%d kinds:",n);      /*输出结果*/
    for(k=0;a[k];k++)
        printf("%d ",a[k]);
    printf("\n");
}
*运行结果
        19 kinds: 5  10  15  3  8  13  18  6  11  16  21  9  14  19  24  12  17  22  27

-------------------------------------------------------------

73 和数能表示1~23的5个正整数
    已知五个互不相同的正整数之和为23，且从这五个数中挑选若干个加起来可以表示从1到23之内的全部自然数。问这五个数是什么？
*问题分析与算法设计
    从计算机程序设计的角度来说，可以用穷举法分解23，然后判定所分解的五个数是否可以表示1到23 之间的全部整数。
*程序与程序注释
#include<stdio.h>
void main()
{
   int a,b,c,d,e,i,j,k,l,m,x,count=0,f=0;  /*f:分解的5个数可以表示出1~23的标记*/
   printf("There are following possble result:\n");
   for(a=1;a<=23;a++)         /*将23分解为a,b,c,d,e五个数*/
      for(b=1+a;b<=23-a;b++)
         for(c=1+b;c<=23-a-b;c++)
            for(d=1+c;d<=23-a-b-c;d++)
            {
               f=1;
               if((e=23-a-b-c-d)>d)
                  for(f=0,x=1;x<24&&!f;x++)     /*判定5个数可否表示1~23*/
                     for(f=1,i=0;i<2&&f;i++)    /*穷举5个数的全部取舍*/ 
                        for(j=0;j<2&&f;j++)
                           for(k=0;k<2&&f;k++)
                              for(l=0;l<2&&f;l++)
                                 for(m=0;m<2&&f;m++)
                                    if(x==a*i+b*j+c*k+d*l+e*m) f=0;
               if(!f) printf("[%d]: %d %d %d %d %d\n",++count,a,b,c,d,e);
            }
}
*运行结果
      There are following possble result:
      [1]: 1 2 3 5 12
      [2]: 1 2 3 6 11
      [3]: 1 2 3 7 10
      [4]: 1 2 4 5 11
      [5]: 1 2 4 6 10
      [6]: 1 2 4 7 9

上一篇：{实例}C趣味程序百例(21) 人气:7154
下一篇：{实例}C趣味程序百例(24) 人气:5842

C语言程序设计视频教程