北理C语言作业及答案3.doc

C语言作业3
43. 缩写展开
成绩: 10 / 折扣: 0.8
在保存字符串时，对出现在连续位置的若干个字符，如这些字符在ASCII表中也是连续出现，则可以将这些字符使用缩写形式进行保存，以节省保存空间。例如用A-Z表示ABCD...XYZ，1-5表示12345，c-f表示cdef。
输入：
包含缩写形式的字符串
输出：
将缩写形式进行还原后的字符串
说明：
只分别对大写字母、小写字母和数字进行压缩，对于形如9-A，a-C这样的缩写不进行处理。

测试输入
期待的输出
时间限制
内存限制
额外进程
测试用例 1
以文本方式显示
1. 0-9↵
以文本方式显示
1. 0123456789↵
1秒
64M
0
测试用例 2
以文本方式显示
1. G-I↵
以文本方式显示
1. GHI↵
1秒
64M
0
测试用例 3
以文本方式显示
1. ABDG-K035-9abd-h↵
以文本方式显示
1. ABDGHIJK0356789abdefgh↵
1秒
64M
0
测试用例 4
以文本方式显示
1. abcdef ghi jkl mn↵
以文本方式显示
1. abcdef ghi jkl mn↵
1秒
64M
0
测试用例 5
以文本方式显示
1. 1-1↵
以文本方式显示
1. 1-1↵
1秒
64M
0
#include <stdio.h>
int main()
{
int i=0;
char s[100];
gets(s);
while(s[i]!='\0')
{
if(s[i+1]!='-')
{
printf("%c",s[i]);
i++;
}
else
{
if(s[i+2]>s[i] && ((s[i]<=57)+(s[i+2]<=57)!=1) && (s[i]<=57||s[i]>=65))
{
while(s[i]!=s[i+2]){
printf("%c",s[i]++);
}
i+=2;
}
else printf("%c",s[i++]);
}
}
printf("\n");
return 0;
}
44. 函数递归
成绩: 10 / 折扣: 0.8
编写一个函数，使用递归算法求满足下述定义的整数序列的第n项。

1
当 n >= 0 且 n <= 4 时
f( n ) =
f(n-1) + f(n-3)
当 n > 4 且n为偶数 时

f(n-2) + f(n-4)
当 n > 4 且n为奇数 时

-1
其他

函数原型如下：

int findf(int n);

参数说明：n 项数；返回值是第n项值。
例如输入：10，输出：8
预设代码
前置代码
view plaincopy to clipboardprint?
1. /* PRESET CODE BEGIN - NEVER TOUCH CODE BELOW */
2.
3. #include <stdio.h>
4.
5. int main()
6. { int n,s, findf( int );
7. scanf("%d", &n);
8. s = findf(n);
9. printf("%d\n", s);
10. return 0;
11. }
12.
13. /* PRESET CODE END - NEVER TOUCH CODE ABOVE */

测试输入
期待的输出
时间限制
内存限制
额外进程
测试用例 1
以文本方式显示
1. 10↵
以文本方式显示
1. 8↵
无限制
64M
0
int findf(int n)
{
if(n>=0&&n<=4)
return 1;
else
if(n>4&&n%2==0)
return findf(n-1) + findf(n-3);
else
if(n>4&&n%2==1)
return findf(n-2) + findf(n-4);
else
return -1;
}
45. 大家再来做游戏
成绩: 10 / 折扣: 0.8
还是那个大家做游戏的问题：
幼儿园的小朋友们刚学习了如何数数，阿姨在下课时组织大家一起玩游戏。规则如下：所有的小朋友绕成一圈，顺序排号，给出开始报数的小孩的编号后，从这个小朋友开始报数，凡是报到固定数字（例如5）的，都退出该游戏，接着从下一个小朋友在从1开始报数，直到只剩下一位小朋友游戏才中止。
输入： 小朋友的个数（<=50） 开始报数的小孩的编号 要被练习的数字
输出： 最终被留下的小朋友的序号
例如输入：4 1 3
输出：The left child is NO 1.
说明：这次，以函数的方式实现上述问题。主函数已经给出，仅需提交自己编写的函数。你可以尝试用递归方法来解决呦！
这个问题是著名的约瑟夫问题，基于著名犹太历史学家 Josephus讲述的一个，所以函数的名字是josephus。
函数原型：
int josephus( int * boy, int n, int m, int r)
参数说明：
int * boy：保存参加游戏的小孩编号的整型数组的首地址。小孩的编号从1开始。
int n：开始参加游戏的小孩总数。
int m：开始时第一次报数的小孩的编号。
int r：要被练习的数字。
预设代码
josephus.c
view plaincopy to clipboardprint?
1. /* PRESET CODE BEGIN - NEVER TOUCH CODE BELOW */
2.
3. #include "stdio.h"
4. int josephus( int *boy, int n, int m, int r );
5.
6. int main( )
7. { int i, boy[50]={0}, n, m, r;
8. scanf("%d%d%d",&n,&m,&r);
9. if( n<=0 || n>50 || m<=0 || m>50 || r<=0 )
10. printf("The number is wrong!\n" );
11. else
12. {
13. for( i=0; i<n; i++ )
14. boy[i] = i + 1;
15. printf( "The left child is NO %d.\n", josephus( boy, n, m, r ) );
16. }
17. return 0;
18. }
19.
20. /* PRESET CODE END - NEVER TOUCH CODE ABOVE */

测试输入
期待的输出
时间限制
内存限制
额外进程
测试用例 1
以文本方式显示
1. 4 1 3↵
以文本方式显示
1. The left child is NO 1.↵
无限制
64M
0
测试用例 2
以文本方式显示
1. 7 2 3↵
以文本方式显示
1. The left child is NO 5.↵
无限制
64M
0
int josephus( int * boy, int n, int m, int r)
{
int j;
if(n>1)
{
if((m+r-1)%n!=0)
{
for(j=(m+r-1)%n-1;j<n-1;j++)
boy[j]=boy[j+1];
return josephus(boy,n-1,(m+r-1)%n,r);
}
else
{
return josephus(boy,n-1,1,r);
}
}
if(n=1)
{
return boy[0];
}
}
H18：拱猪计分（选作）
成绩: 5 / 折扣: 0.8
背景：
拱猪是一种很有趣的扑克牌游戏。即使你不知道它的玩法，你也可以由它的计分方式来了解它的趣味性。 假设在此我们仅考虑四个人的拱猪牌局，本题要求你根据下面的计分规则，在牌局结束时计算四位玩家所得分数。
1. 我们分别以S、H、D及C来代表黑桃，红心，方块及梅花，并以数字1至 13来代表A、2、…、Q、K等牌点，例如：H1为红心A，S13为黑桃K。
2. 牌局结束时，由各玩家持有的有关计分的牌(计分牌)仅有S12(猪)，所有红心牌，D11(羊)及C10(加倍)等16张牌。其它牌均弃置不计。若未持有这16张牌之任一张则以得零分计算。
3. 若持有C10的玩家只有该张牌而没有任何其它牌则得+50分，若除了C10 还有其它计分牌，则将其它计分牌所得分数加倍计算。
4. 若红心牌不在同一家，则H1至H13等13张牌均以负分计，其数值为-50， -2，-3，-4，-5，-6，-7，-8，-9，-10，-20，-30，-40。而且S12与D11分别以-100及+100分计算。
5. 若红心牌H1至H13均在同一家，有下列情形：
o 所有红心牌以+200分计算。
o 若S12、D11皆在吃下所有红心牌之一家，则此玩家得+500分。
o 而C10还是以前面所述原则计算之。
例一：若各玩家持有计分牌如下： ( 每列代表一玩家所持有之牌 )
S12 H3 H5 H13
D11 H8 H9
C10 H1 H2 H4 H6 H7
H10 H11 H12
则各家之得分依序为： -148 、 +83 、 -138 及 -60 。
例二：若各玩家持有计分牌如下：(第四家未持有任何计分牌)
H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 H12 H13
S12 C10
D11
则各家之得分依序为： +200 、 -200 、 +100 及 0 。
例三：若有一玩家持有所有 16 张计分牌，则得 +1000 分。其余三家均得零分。
输入：
每个输入文件由多组测试数据构成，每组测试数据有四行，每一行第一个数为该玩家所持有计分牌总数，而后列出其所持有之所有计分牌，牌数与各计分牌均以一个以上的空格分开。相邻两组测试数据之间不会有空白行，读到四家持牌数都为 0 表示文件结束。
输出：
每一行输出一组测试数据对应的结果，依次输出各家所得分数，共四个整数 ( 含正负号，0 除外)，相邻两个整数之间以一个空格分开，符号和数字间不可以有空格。每组输出间不需要有空白行。

测试输入
期待的输出
时间限制
内存限制
额外进程
测试用例 1
以文本方式显示
1. 4 S12 H3 H5 H13↵
2. 3 D11 H8 H9↵
3. 6 C10 H1 H2 H4 H6 H7↵
4. 3 H10 H11 H12↵
5. 13 H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 H12 H13↵
6. 2 S12 C10↵
7. 1 D11↵
8. 0↵
9. 0↵
10. 0↵
11. 0↵
12. 0↵
以文本方式显示
1. -148 +83 -138 -60↵
2. +200 -200 +100 0↵
1秒
64M
0
#include "stdio.h"
int myinput(int card[],int number[])
{
int i,n;
char s[5];

for(i=0;i<4;i++)
{
scanf("%d",&n);
number[i]=n;
while(n--)
{
scanf("%s",s);
switch(s[0])
{
case 'S':card[13]=i;break;
case 'D':card[14]=i;break;
case 'C':card[15]=i;break;
case 'H':s[2]=='\0'?(card[s[1]-'1']=i):(card[s[2]-'1'+10]=i);
}
}
}
return number[0]+number[1]+number[2]+number[3];
}
int main()
{
int
value[15]={-50,-2,-3,-4,-5,-6,-7,-8,-9,-10,-20,-30,-40,-100,100},
card[16],
score[4]={0,0,0,0},
number[4],
i,s,
input();

while(myinput(card,number))
{
for(i=0,s=0;i<13;i++)
s+=card[i];
if(s%13)
{
for(i=0;i<15;i++)
score[card[i]]+=value[i];
}
else
{
if(card[0]==card[13]&&card[13]==card[14])
score[card[0]]+=500;
else
{
score[card[0]]+=200;
score[card[14]]+=value[14];
score[card[13]]+=value[13];
}
}
score[card[15]]+=number[card[15]]==1?50:score[card[15]];
for(i=0;i<4;i++)
printf("%s%d%s",score[i]>0?"+":"",score[i],i==3?"\n":" ");
for(i=0;i<4;i++)
score[i]=0;
}
return 0;
}
46 求表示方法
成绩: 10 / 折扣: 0.8
设 m、n 均为自然数，m 可表示为一些不超过 n 的自然数之和，f(m,n) 为这种表示方式的数目。
例如，f(5,3)=5，有5种表示方法：3+2，3+1+1，2+2+1，2+1+1+1，1+1+1+1+1。
请编写程序，计算f(m,n)的值。
输入：
m n
输出：
f(m,n)的值

测试输入
期待的输出
时间限制
内存限制
额外进程
测试用例 1
以文本方式显示
1. 5 3↵
以文本方式显示
1. 5↵
1秒
64M
0
测试用例 2
以文本方式显示
1. 6 4↵
以文本方式显示
1. 9↵
1秒
64M
0
#include<stdio.h>
int f(int y,int x)
{
if(y==1) return 1;
if(x==1) return 1;
if(y<x) return f(y,y);
if(x==y) return 1+f(y,x-1);
return f(y,x-1)+f(y-x,x);
}
main()
{
int m,n;
scanf("%d%d",&m,&n);
printf("%d\n",f(m,n));
}
#include<stdio.h>
int f(int y,int x)
{
if(y==1) return 1;
if(x==1) return 1;
if(y<x) return f(y,y);
if(x==y) return 1+f(y,x-1);
return f(y,x-1)+f(y-x,x);
}
main()
{
int m,n;
scanf("%d%d",&m,&n);
printf("%d\n",f(m,n));
}
#include<stdio.h>
char * search(char *str, char ch)
{
char *A=NULL, *B=NULL;
int Temp, Count=0;
while(*str)
{
if(*str == ch)
{ Temp = 0;
A = str;
while(*str == ch)
++Temp, ++str;
if(Temp > Count)
Count = Temp, B = A;
if(!*str) break;}
++str;
}
return B;
}
48.元素值之和
成绩: 5 / 折扣: 0.8
编写函数，计算给定的整型数组的奇数元素值之和、偶数元素值之和。
例如数组元素的值依次为： 1 ， 8 ， 2 ， 3 ， 11 ， 6 ；则奇数值之和 15 、偶数值之和 16 。
函数原型： void findsum( int *pa , int n, int *podd, int *peven ) 。
参数说明： pa 是整型数组的首地址， n 是数组元素个数(元素个数不大于100)，指针 podd 、 peven 保存奇数之和、偶数之和的整型变量的地址。
返回值：无返回值。
预设代码
findsum_48.c
view plaincopy to clipboardprint?
1. /* PRESET CODE BEGIN - NEVER TOUCH CODE BELOW */
2.
3. #include <stdio.h>
4.
5. void findsum( int *pa, int n, int *podd, int *peven );
6.
7. main( )
8. {
9. int i, n, a[100], odd, even;
10. scanf( "%d",&n );
11. for( i=0; i<n; i++ )
12. scanf("%d",&a[i] );
13. findsum( a, n, &odd, &even );
14. printf("odd=%d,even=%d\n", odd, even );
15. }
16.
17. /* PRESET CODE END - NEVER TOUCH CODE ABOVE */

测试输入
期待的输出
时间限制
内存限制
额外进程
测试用例 1
以文本方式显示
1. 6↵
2. 1 8 2 3 11 6↵
以文本方式显示
1. odd=15,even=16↵
无限制
64M
0
测试用例 2
以文本方式显示
1. 1↵
2. 0↵
以文本方式显示
1. odd=0,even=0↵
无限制
64M
0
void findsum( int *pa, int n, int *podd, int *peven )
{
int i;
*podd=0;
*peven=0;
for(i=0;i<n;i++)
{ if(pa[i]%2)
*podd=*podd+pa[i];
else
*peven=*peven+pa[i];}
}
void findsum( int *pa, int n, int *podd, int *peven )
{
int i;
*podd=0;
*peven=0;
for(i=0;i<n;i++)
{ if(pa[i]%2)
*podd=*podd+pa[i];
else
*peven=*peven+pa[i];}
}
#include<stdio.h>

#include<string.h>

#include<math.h>

#define MAX 100

int run(char input[])

{

int length=strlen(input);//获得字符串长度

int i;

int k;

int m;

int mn;

int temp;

int num[MAX],j=0;

int w[10],iw=0;

for(i=0;i<MAX;i++) num[i]=0;

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

{

if(input[i]=='*')

{

temp=num[j-2]*num[j-1];

j=j-2;

for(k=j+1;k<MAX;k++)num[k]=0;

num[j]=temp;

}

else if(input[i]=='/')

{

temp=num[j-2]/num[j-1];

j=j-2;

for(k=j+1;k<MAX;k++)num[k]=0;

num[j]=temp;

}

else if(input[i]=='+')

{

temp=num[j-2]+num[j-1];

j=j-2;

for(k=j+1;k<MAX;k++)num[k]=0;

num[j]=temp;

}

else if(input[i]=='-')

{

temp=num[j-2]-num[j-1];

j=j-2;

for(k=j+1;k<MAX;k++)num[k]=0;

num[j]=temp;

}

else if(input[i]==' ')//空格表示一个数字输入完毕

{

mn=0;

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

{

num[j]=num[j]+w[mn]*pow(10,m);

mn++;

}

j++;iw=0;

}

else

{ //int w[10],iw=0;

//num[j]=num[j]+(int)input[i]-48;

w[iw]=(int)input[i]-48;

iw++;

}

}

return num[0];

}

void main()

{

char input[MAX];

gets(input);

int result;

result=run(input);

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

}
#include<stdio.h>

#include<string.h>

#include<math.h>

#define MAX 100

int run(char input[])

{

int length=strlen(input);//获得字符串长度

int i;

int k;

int m;

int mn;

int temp;

int num[MAX],j=0;

int w[10],iw=0;

for(i=0;i<MAX;i++) num[i]=0;

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

{

if(input[i]=='*')

{

temp=num[j-2]*num[j-1];

j=j-2;

for(k=j+1;k<MAX;k++)num[k]=0;

num[j]=temp;

}

else if(input[i]=='/')

{

temp=num[j-2]/num[j-1];

j=j-2;

for(k=j+1;k<MAX;k++)num[k]=0;

num[j]=temp;

}

else if(input[i]=='+')

{

temp=num[j-2]+num[j-1];

j=j-2;

for(k=j+1;k<MAX;k++)num[k]=0;

num[j]=temp;

}

else if(input[i]=='-')

{

temp=num[j-2]-num[j-1];

j=j-2;

for(k=j+1;k<MAX;k++)num[k]=0;

num[j]=temp;

}

else if(input[i]==' ')//空格表示一个数字输入完毕

{

mn=0;

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

{

num[j]=num[j]+w[mn]*pow(10,m);

mn++;

}

j++;iw=0;

}

else

{ //int w[10],iw=0;

//num[j]=num[j]+(int)input[i]-48;

w[iw]=(int)input[i]-48;

iw++;

}

}

return num[0];

}

void main()

{

char input[MAX];

gets(input);

int result;

result=run(input);

printf("%d\n",result); #include<stdio.h>

#include<string.h>

#include<math.h>

#define MAX 100

int run(char input[])

{

int length=strlen(input);//获得字符串长度

int i;

int k;

int m;

int mn;

int temp;

int num[MAX],j=0;

int w[10],iw=0;

for(i=0;i<MAX;i++) num[i]=0;

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

{

if(input[i]=='*')

{

temp=num[j-2]*num[j-1];

j=j-2;

for(k=j+1;k<MAX;k++)num[k]=0;

num[j]=temp;

}

else if(input[i]=='/')

{

temp=num[j-2]/num[j-1];

j=j-2;

for(k=j+1;k<MAX;k++)num[k]=0;

num[j]=temp;

}

else if(input[i]=='+')

{

temp=num[j-2]+num[j-1];

j=j-2;

for(k=j+1;k<MAX;k++)num[k]=0;

num[j]=temp;

}

else if(input[i]=='-')

{

temp=num[j-2]-num[j-1];

j=j-2;

for(k=j+1;k<MAX;k++)num[k]=0;

num[j]=temp;

}

else if(input[i]==' ')//空格表示一个数字输入完毕

{

mn=0;

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

{

num[j]=num[j]+w[mn]*pow(10,m);

mn++;

}

j++;iw=0;

}

else

{ //int w[10],iw=0;

//num[j]=num[j]+(int)input[i]-48;

w[iw]=(int)input[i]-48;

iw++;

}

}

return num[0];

}

void main()

{

char input[MAX];

gets(input);

int result;

result=run(input);

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

}

}
49.为整数编号
成绩: 10 / 折扣: 0.8
使用以下结构
struct nn
{
int no;
int num;
};
建立一个结构数组，从键盘输入若干个整数，保存在数组元素的num成员中，并根据输入的数按从小到大进行编号，将编号保存在no成员中。按整数的输入顺序输出整数及其编号。输入的整数不超过100个，每个整数的绝对值不大于1000，输入时以空格分隔整数。
例如输入：4 3 6 8 2 3 9
输出：
4 4
3 2
6 5
8 6
2 1
3 3
9 7
要求：当两个整数相等时，整数的排列顺序由输入的先后次序决定。例如：输入的第2个整数为3，第6个整数也为3，则将先输入的整数3的编号在前，后输入的整数3的编号在后。编写函数完成为整数编号。
函数原型：int number( char *str, struct nn a[] );
其中：str：保存以字符串方式接收的键盘输入，
a： 保存整数及编号的结构数组的首地址，
函数返回值：已输入的整数的个数。
预设代码
前置代码
view plaincopy to clipboardprint?
1. /* PRESET CODE BEGIN - NEVER TOUCH CODE BELOW */
2.
3. #include <stdio.h>
4. struct nn
5. { int no;
6. int num;
7. };
8.
9. typedef struct nn DATA;
10.
11. int number( char * , DATA []);
12.
13. int main( )
14. {
15. DATA b[100];
16. char sa[500];
17. int i, n;
18. gets( sa );
19. n = number( sa, b );
20. for ( i=0; i<n; i++ )
21. printf("%d %d\n", b[i].num, b[i].no );
22. return 0;
23. }
24.
25. /* Here is waiting for you
26. int number( char * str, DATA a[] )
27. {
28. ....
29. }
30. */
31.
32. /* PRESET CODE END - NEVER TOUCH CODE ABOVE */

测试输入
期待的输出
时间限制
内存限制
额外进程
测试用例 1
以文本方式显示
1. 4 3 6 8 2 3 9↵
以文本方式显示
1. 4 4↵
2. 3 2↵
3. 6 5↵
4. 8 6↵
5. 2 1↵
6. 3 3↵
7. 9 7↵
无限制
64M
0
测试用例 2
以文本方式显示
1. 1 1 1 1