第八届程序设计大赛初赛试题及答案

说明：请将所有答案写到试卷第1页及第2页。

1、读程序写结果（40分）

1、（5分）                        2、（5分）                        3、（10分）

结果：                            结果：                            结果：

4、（10分）                    5、（5分）                        6、（5分）

结果：                            结果：                            结果：

2、代码填空（30分）

1、（5分）                                    2、（5分）

空一：____acm / lg    （5分）                 空一： if(begin>end) return （5分）

3、（12分）                                    4、（8分）

空一：        siruan /= 10       （3分）         空一：      s[i] - '0'            （4分）

空二：      hm - lg             （3分）         空二：    siruan[sum % 11]      （4分）

空三：      lghm = acm(lghm)    （6分）     

3、思维题（15分）

数据1：T1=1，T2=2， T3=3， T4 = 4                数据2：T1=1，T2=2， T3=5， T4 = 10

答案：（acm）1 2->(siruan) 2min 答案：（acm）1 2->(siruan) 2min

(acm) <-1 (siruan) 1min (acm) <-1 (siruan) 1min

(acm) 1 3->(siruan) 3min (acm) 5 10->(siruan) 10min

(acm) <-1 (siruan) 1min (acm) <-2 (siruan) 2min

(acm) 1 4-> (siruan) 4min (acm) 1 2-> (siruan) 2min

 最短时间：2+1+3+1+4 = 11min                       最短时间：2+1+10+2+2 = 17min

数据3：T1 = 5， T2 = 2， T3=1， T4=10， T5=8

答案：（acm）1 2->(siruan) 2min

(acm) <-1 (siruan) 1min

(acm) 8 10->(siruan) 10min

(acm) <-2 (siruan) 2min

(acm) 1 2-> (siruan) 2min

(acm) <-1 (siruan) 1min

(acm) 1 5 ->(siruan) 5min

  最短时间：2+1+10+2+2+1+5 = 23min

4、编程题（15分）

程序代码：

#include

#include

int s[110];

int main()

{

    int i;

    int a, n, m;

    while (scanf("%d%d", &a, &n)!=EOF)

    {

        memset(s, 0x00, sizeof(s));

        m = n;

for (i=0; i        {

            s[i] += a * (n--);

            s[i+1] = s[i] / 10;

            s[i] %= 10;

        }

        if (s[m]) printf("%d", s[i]);

for (i=m-1; i>=0; i--)

            printf("%d", s[i]);

        printf("\\n");

    }

    return 0;

}

一、读程序写结果（40分）

1、（5分）

#include

int main()

{

    char acm[] = "I love acm!";

    char siruan[] = "I love siruan!";

    char def[] = "Welcome to join us!";

    int chose = 0;

    switch (chose)

    {

        case 0: printf("%s\\n", acm);

        case 1: printf("%s\\n", siruan);

        default : printf("%s", def);

    }

    return 0;

}

输出结果：

2.（5分）

#include

int main()

{

    int acm = 0, siruan = 1;

    if (acm = siruan) printf("%s", "May you success!");

    else printf("%s", "May you success,too!");

    return 0;

}

输出结果：

3.（10分）

#include

#include

int main()

{

    int i,j,k,n;

    char lghm[14]="ILOVEACMSIRUAN";

    n = 3;

for (i=0; i    printf("%c\\n",lghm[0]);

for (i=1; ifor (j=abs(n-i-1); j>0; j--) //abs(n)返回值为整形n的绝对值

            printf(" ");

        printf("%c",lghm[2*i-1]);

for (k=1; k<=2*i-1; k++) printf(" ");

        printf("%c\\n",lghm[2*i]);

    }

for (i=n; i<=2*n-3; i++){

for (j=abs(n-i-1); j>0; j--) printf(" ");

        printf("%c",lghm[2*i-1]);

for (k=1; k<=4*n-5-2*i; k++) printf(" ");

        printf("%c\\n",lghm[2*i]);

    }

for (i=0; i    printf("%c\\n",lghm[4*n-5]);

    return 0;

}

输出结果：

4.（10分）

#include

#include

struct Student

{

    char name[20];

    int num;

} stu[5];

void init()

{

    stu[0].num = 521; strcpy(stu[0].name, "sichuan wenchuan");

    stu[1].num = 521; strcpy(stu[1].name, "bless");

    stu[2].num = 420; strcpy(stu[2].name, "sichuan yaan");

    stu[3].num = 420; strcpy(stu[3].name, "love");

    stu[4].num = 420; strcpy(stu[4].name, "god");

}

void swap(int a, int b)

{

    struct Student tmp;

    tmp.num = stu[a].num;

    stu[a].num = stu[b].num;

    stu[b].num = tmp.num;

    strcpy(tmp.name, stu[a].name);

    strcpy(stu[a].name, stu[b].name);

    strcpy(stu[b].name, tmp.name);

}

void bubble_sort(int n)

{

    int i,j,flag,temp;

for(i = 0; i < n-1; i++){

        flag = 1;

for(j = 0; j < n-i-1; j++){

if(stu[j].num > stu[j+1].num){

                swap(j, j+1);

                flag = 0;

            }

else if (stu[j].num == stu[j+1].num && strcmp(stu[j].name,stu[j+1].name)<0){

                swap(j, j+1);

            }

        }

        if(flag) break;

    }

}

int main()

{

    init();

    bubble_sort(5);

    int i;

for (i=0; i<5; i++)

        printf("%-4d%s\\n", stu[i].num, stu[i].name);

    return 0;

}

输出结果：

6.（5分）

#include

int acm()

{

    int lg = 1314520;

    int hm = 0;

while(lg > 0)

    {

        hm = hm * 10 + lg % 10;

        lg /= 10;

    }

    return hm;

}

int main()

{

    int siruan = acm();

    printf("%d", siruan);

    return 0;

}

输出结果：

2、代码填空（30分）

1.(5)

如果没有计算器，我们如何求3的平方根？

可以先猜测一个数，比如1.5，然后用3除以这个数字。如果我们猜对了，则除法的结果必然与我们猜测的数字相同。我们猜测的越准确，除法的结果与猜测的数字就越接近。

根据这个原理，只要我们每次取猜测数和试除反馈数的中间值作为新的猜测数，肯定更接近答案！这种计算方法叫做“迭代法”。

下面的代码模拟了如何用手工的方法求3的平方根的过程。请填写缺少的代码。    

#include

#include

int main()

{

    double acm = 3;

    double lg = 0;

    double hm = acm;

while(fabs(lg-hm)>1E-15)

    {

        lg = (lg+hm)/2;

        hm = ________________;      // 填空

    }

    printf("%lf\\n", lg);

    return 0;

}

2（5分）

以下程序打印出0~9的数字，请补充缺少的代码。

#include

void acm(int begin, int end)

{

    _____________________;          // 填空

    printf("%d ", begin);

    acm(begin+1, end);

}

int main()

{

    acm(0,9);

    return 0;

}

3(12分)

任意给定一个4位数(不能所有位都相同)，比如：5210，重新组合出最大数：5210，再重新组合出最小数：125，相减，得到新的4位数（如不足则补0），重复这个过程，最后必然得到一个数字：6174。这个现象被称为：数字黑洞。下面的函数实现由给定的4位整数求出下一个整数的功能。请完善之。

#include

int acm(int siruan)

{

    int N[4];

    int i, j;

for(i=0; i<4; i++){

        N[3-i] = siruan % 10;

        ______________________;      // 填空

    }

for(i=0; i<3; i++)

     for(j=0; j<3-i; j++)if(N[j]>N[j+1]){

                int t = N[j+1];

                N[j+1] = N[j];

                N[j] = t;

            }

    int lg = 0;

for(i=0; i<4; i++)

        lg = lg * 10 + N[i] ;

    int hm = 0;

for(i=3; i>=0; i--)

        hm = hm * 10 + N[i];

    return _________________;          // 填空

}

int main()

{

    int i;

    int lghm = 5210;

for (i=0; i<10; i++)

    {

        ______________________;          // 填空

        printf("%d\\n", lghm);

        if (6174 == lghm) break;

    }

    return 0;

}

4.(8分)

Hello，大家好，欢迎大家参加第八届中北大学程序设计竞赛（山西首届思软杯），这次的报名系统相信大家都用过吧，潘老师（我们校acm队的教练）怕有人乱报名，所以要将各位同学输入自己的身份证号（只是为了验证信息，绝对没有公布哦）。其实验证方法很简单：

例如：身份证前17位 = ABCDEFGHIJKLMNOPQ ，A~Q 每位数字乘以权值求和（每位数字和它对应的“权”相乘后累加）17位对应的权值分别是：7 9 10 5 8 4 2 1 6 3 7 9 10 5 8 4 2

求出的总和再对11求模。然后按下表映射：

  余数     0   1   2   3   4   5   6   7   8   9   10 

  校验码： 1   0   X   9   8   7   6   5   4   3   2 

  下面的代码实现了校验过程，输入串为身份证前17位，打印出校验码。

#include

char acm(char* s)

{

    static int weight[] = {7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2};

    static char siruan[] = {'1','0','X','9','8','7','6','5','4','3','2'};

    int sum = 0;

    int i;

for(i=0; i<17; i++){

        sum += (__________________) * weight[i];  // 填空

    }

    return __________________________;  // 填空

}

int main()

{

    char lghm[] = "370785191016000";

    printf("%c", acm(lghm));

    return 0;

}

3、思维题目（15分）

一个晚上有N个人想要过一个独木桥，各个人通过这个独木桥需要时间为Ti，晚上，需要手电筒照明，但是手电筒只有一个，独木桥每次只允许两个人通过，两个人一起过桥需要的时间和速度慢的人通过独木桥的时间相同（这个好理解，快的当然要等着慢的了），问最少需要多长时间才能使所有的人通过独木桥。(桥的两岸分别用(acm)和(siruan)代替)

你需要算出下面的例子中最短的时间并且把过桥方案写出来。

如：N=3时 T1 = 1 ，T2 = 2 ，T3=3则你需要这样回答本题：

过桥方案：（acm）1 2->（siruan）  2min

         （acm）<-1(siruan) 1min

(acm)1 3->(siruan) 3min

最短时间为：2+1+3 = 6min

数据1：T1=1，T2=2， T3=3， T4 = 4

过桥方案：

最短时间为：

数据2：T1=1，T2=2， T3=5， T4 = 10

过桥方案：

最短时间为：

数据3：T1 = 5， T2 = 2， T3=1， T4=10， T5=8

过桥方案：

最短时间为：

五、编程题（15分）：

中北大学于2005年开始正式参加ACM/ICPC国际大学生程序设计竞赛，国内历年亚洲预选赛征战的足迹包括北京、杭州、宁波、大连、哈尔滨、长春、天津等地，并多次在亚洲预选赛中获奖，为学校争得了荣誉！ACM/ICPC最具有挑战性，ACM/ICPC最具有趣味性。畅游在数据结构和算法的海洋中，聆听键盘与代码的交响乐，Just Join us！我们需要继续超越自我。我们需要再创高峰。We  Need  You！我们会通过本次比赛选拔一批新队员，大家加油了~

此题很简单啊，就是给定了整数a和n，计算a+aa+aaa+a...a(n个a)的和。

输入数据有多组，要求从键盘输入a，n（1<=a<=9,1<=n<=100，输入一定符合要求，不需要判断是否在此范围内）。每一次输入完成后回车则立刻计算出结果，并向屏幕输出。C语言中多组数据的输入用while（scanf("%d%d", &a, &n)！=EOF）完成。

输出：对于从键盘输入的a和n,请输出您计算上式的结果。

例如：第一行为用户输入数据2 2，即你需要计算出2+22=24，则将你计算的结果24直接输出到屏幕（上图第二行）。第三行为用户1 10，则你需要计算出 1+11+....+1111111111 = 1234567900，则将你计算的结果1234567900直接输出到屏幕（上图第四行）。

代码：