C语言谁家孩子跑的最慢问题

时间：12-29来源：作者：点击数：90

问题描述

假设有张王李三家，每家都有3个孩子。某一天，这三家的9个孩子一起比赛短跑，规定不考虑年龄大小，第1名得9分，第2名得8分，第3名得7分，依次类推。比赛结束后统计分数发现三家孩子的总分是相同的，同时限定这9个孩子的名次不存在并列的情况，且同一家的孩子不会获得相连的名次。现已知获得第1名的是李家的孩子，获得第2名的是王家的孩子，要求编程求出获得最后一名的是哪家的孩子。

问题分析

根据问题描述可知：

(1) 参加比赛的一共有9个孩子，得分情况依次是从1分〜9分。由此可知，该场比赛总共的分数为9+8+7+6+5+4+3+2+1=45分。

(2) 由于“比赛结束后统计分数发现三家孩子的总分是相同的”，因此每家孩子的得分都为15分。

(3) 由于“获得第一名的是李家的孩子，获得第二名的是王家的孩子”，因此可推知获得第三名的一定是张家的孩子，否则李家（或王家）的孩子总分就会超过15分。

(4) 由于“这9个孩子的名次不存在并列的情况，且同一家的孩子不会获得相连的名次”，因此可推知获得第4名的一定不是张家的孩子。

算法设计

将问题分析中的文字进一步具体化。

先确定使用什么结构来存储九个孩子的分数，这里考虑使用二维数组，设数组名为score，且score[1]中存放张家3个孩子的分数，score[2]中存放王家3个孩子的分数，score[3]中存放李家3个孩子的分数。因为“同一家的孩子不会获得相连的名次”，则张家3个孩子的分数分别按由大到小的顺序依次存放在数组元素score[1][1]、score[1][2]和score[1][3]中；王家3个孩子的分数分别按由大到小的顺序依次存放在数组元素score[2][1]、score[2][2]和score[2][3]中，李家3个孩子的分数分别按由到大到小的顺序依次存放在数组元素score[3][1]、score[3][2]和score[3][3]中。

因此，由问题分析中第（2）点可知：
score[1][1]+score[1][2]+score[1][3]=15
score[2][1]+score[2][2]+score[2][3]=15
score[3][1]+score[3][2]+score[3][3]=15 ①

由问题分析中第（3）点可知：
score[3][1]=9，score[2][1]=8，而score[l][1]=7 ②

由问题分析中第（4）点可知：score[1][2]≠6

由于“9个孩子的名次不存在并列的情况，且同一家的孩子不会获得相连的名次”，因此score数组中存放的9个值应该各不相同，分数为1〜9。由①、②可推知
：score[1][2]+score[1][3]≠score[2][2]+score[2][3]≠score[3][2]+score[3][3]

因为9个孩子的名次不会并列，且每家孩子的分数是按大小顺序依次存放在二维数组中的，因此：
score[1][2]+score[2][2]≠score[3][2]
score[1][3]+score[2][3]≠score[3][3] ③

且score[1][2]、score[2][2]、score[3][2]应该占据了分数段的4〜6分这几个分值，score[1][3]、score[2][3]、score[3][3]则占据了分数段的1〜3分这几个分值。

由上面分析可知，由于己经明确了score[1][2]、score[2][2]、score[3][2]这3个数组元素中存放的值所占据的分数段为4分〜6分，则可以使用循环结构来判断出3个元素中存放的值分别是几。判断的依据是在循环体中检测，保证③的成立。

下面是完整的代码：

#include <stdio.h>
int main()
{
    int score[4][4];
    int zhang, wang, li, last, i, j;
    score[1][1]=7;  /*score[1]存放张家三个孩子的分数*/
    score[2][1]=8;  /*score[2]存放王家三个孩子的分数*/
    score[3][1]=9;  /*score[3]存放李家三个孩子的分数*/
    for(zhang=4; zhang<6; zhang++)  /*张家孩子在4到6分段可能取值的分数为4,5，不能取6*/
        for(wang=4; wang<7; wang++)  /*王家孩子在4到6分段可能取值的分数为4,5,6*/
            for(li=4; li<7; li++)  /*李家孩子在4到6分段可能取值的分数为4,5,6*/
                if(zhang!=wang && li!=zhang && li!=wang
                   && 15-zhang-score[1][1]!=15-wang-score[2][1]  /*9个孩子名次不存在并列的情况*/
                   && 15-zhang-score[1][1]!=15-li-score[3][1]
                   && 15-wang-score[2][1]!=15-li-score[3][1])
                {
                    score[1][2]=zhang;  /*将结果存入对应的数组元素*/
                    score[1][3]=15-zhang-7;
                    score[2][2]=wang;
                    score[2][3]=15-wang-8;
                    score[3][2]=li;
                    score[3][3]=15-li-9;
                }
   
    printf("array score:\n");  /*打印二维数组score，输出各家孩子的分数*/
    for(last=0, i=1; i<=3; i++)
        for(j=1; j<=3; j++)
        {
            printf("%d", score[i][j]);
            printf(" ");
            if(j == 3)
                printf("\n");  /*每输入三个值换行*/
            if(score[i][j] == 1)
                last=i;  /*记录最后一名孩子所来自的家庭*/
        }
    /*输出最后一名孩子来自的家庭*/
    if(last == 1)
        printf("The last one reached the end is a child from family Zhang.\n");
    else if(last == 2)
        printf("The last one reached the end is a child from family Wang.\n");
    else
        printf("The last one reached the end is a child from family Li.\n");
   
    return 0;
}