计算机学院ACM程序设计竞赛题目.docx
- 文档编号:5716084
- 上传时间:2023-05-09
- 格式:DOCX
- 页数:20
- 大小:20.37KB
计算机学院ACM程序设计竞赛题目.docx
《计算机学院ACM程序设计竞赛题目.docx》由会员分享,可在线阅读,更多相关《计算机学院ACM程序设计竞赛题目.docx(20页珍藏版)》请在冰点文库上搜索。
计算机学院ACM程序设计竞赛题目
2011年计算机学院程序设计竞赛题目
比赛时间:
2011.3.1下午3:
00 120分钟;
比赛地点:
计算机实验室206
比赛要求:
1、建立学院+年级+姓名为文件夹,将所编写的程序存放在文件夹中。
2、根据题目要求设计求解问题的算法,写出解题的关键点,采用你所熟悉的语言实现算法并测试。
注意程序变量命名规范化、程序行间要有合理的缩进。
题目一 寻找大富翁
ProblemDescription
信阳市共有n个人,请找出该市的前m个大富翁。
Input
输入包含多组测试用例。
每个用例首先包含2个整数n(0 n为信阳市的人数,m为需要找出的大富翁数,接下来一行输入市内n个人的财富值。 n和m同时为0时表示输入结束。 Output 请输出信阳市前m个大富翁的财产数,财产多的排前面,如果大富翁不足m个,则全部输出,每组输出占一行。 SampleInput 31 25-1 53 12345 00 SampleOutput 5 543 题目二 xxx定律 ProblemDescription 对于一个数n,如果是偶数,就把n砍掉一半;如果是奇数,把n变成3*n+1后砍掉一半,直到该数变为1为止。 请计算需要经过几步才能将n变到1,具体可见样例。 Input 输入包含多组测试用例。 每个用例包含一个整数n,当n为0时表示输入结束。 (1<=n<=10000)。 Output 对于每组测试用例请输出一个数,表示需要经过的步数,每组输出占一行。 SampleInput 3 1 0 SampleOutput 5 0 题目三 A+B ProblemDescription 读入两个小于100的正整数A和B,计算A+B。 需要注意的是: A和B的每一位数字由对应的英文单词给出。 Input 测试输入包含若干测试用例,每个测试用例占一行,格式为"A+B=",相邻两字符串有一个空格间隔。 当A和B同时为0时输入结束,相应的结果不要输出。 Output 对每个测试用例输出1行,即A+B的值。 SampleInput one+two= threefour+fivesix= zeroseven+eightnine= zero+zero= SampleOutput 3 90 96 题目四 百岛湖 ProblemDescription 相信大家都听说一个“百岛湖”的地方吧,百岛湖的居民生活在不同的小岛中,当他们想去其他的小岛时都要通过划小船来实现。 现在政府决定大力发展百岛湖,发展首先要解决的问题当然是交通问题,政府决定实现百岛湖的全畅通! 经过考察小组RPRush对百岛湖的情况充分了解后,决定在符合条件的小岛间建上桥,所谓符合条件,就是2个小岛之间的距离不能小于10米,也不能大于1000米。 当然,为了节省资金,只要求实现任意2个小岛之间有路通即可。 其中桥的价格为100元/米。 Input 输入包括多组数据。 输入首先包括一个整数T(T<=200),代表有T组数据。 每组数据首先是一个整数C(C<=100),代表小岛的个数,接下来是C组坐标,代表每个小岛的坐标,这些坐标都是0<=x,y<=1000的整数。 Output 每组输入数据输出一行,代表建桥的最小花费,结果保留一位小数。 如果无法实现工程以达到全部畅通,输出”oh! ”。 SampleInput 2 2 1010 2020 3 11 22 10001000 SampleOutput 1414.2 oh! 题目五 Howmanyways? ? ProblemDescription 春天到了,校园里开满了花,姹紫嫣红,非常美丽。 葱头是个爱花的人,看着校花校草竞相开放,漫步校园,心情也变得舒畅。 为了多看看这迷人的校园,葱头决定,每次上课都走不同的路线去教室,但是由于时间问题,每次只能经过k个地方,比方说,这次葱头决定经过2个地方,那他可以先去明德广场看看喷泉,再去教室,也可以先到体育场跑几圈,再到教室。 他非常想知道,从A点恰好经过k个点到达B点的方案数,当然这个数有可能非常大,所以你只要输出它模上1000的余数就可以了。 你能帮帮他么? ? 你可决定了葱头一天能看多少校花哦。 Input 输入数据有多组,每组的第一行是2个整数n,m(0< n<=20,m<=100)表示校园内共有n个点,为了方便起见,点从0到n-1编号,接着有m行,每行有两个整数s,t(0<=s,t 接着的一行是整数T,表示有T组询问(1<=T<=100),接下来的T行,每行有三个整数A,B,k,表示问你从A点到B点恰好经过k个点的方案数(k< 20),可以走重复边。 如果不存在这样的走法,则输出0。 当n,m都为0的时候输入结束。 Output 计算每次询问的方案数,由于走法很多,输出其对1000取模的结果。 SampleInput 44 01 02 13 23 2 032 033 36 01 10 02 20 12 21 2 121 013 00 SampleOutput 2 0 1 3 参考答案代码 A + B Problem Description 读入两个小于100的正整数A和B,计算A+B。 需要注意的是: A和B的每一位数字由对应的英文单词给出。 Input 测试输入包含若干测试用例,每个测试用例占一行,格式为"A + B =",相邻两字符串有一个空格间隔。 当A和B同时为0时输入结束,相应的结果不要输出。 Output 对每个测试用例输出1行,即A+B的值。 Sample Input one + two = three four + five six = zero seven + eight nine = zero + zero = Sample Output 3 90 96 */ #include #include #include struct InPutString { char Value[100];//每次输入的计算字符串 InPutString * Next;//指向下一个结构体的地址 }; int WordsToInt(char * Value)//单个单词转换为整数值 { if (strcmp("one", Value) == 0) return 1; else if (strcmp("two", Value) == 0) return 2; else if (strcmp("three", Value) == 0) return 3; else if (strcmp("four", Value) == 0) return 4; else if (strcmp("five", Value) == 0) return 5; else if (strcmp("six", Value) == 0) return 6; else if (strcmp("seven", Value) == 0) return 7; else if (strcmp("eight", Value) == 0) return 8; else if (strcmp("nine", Value) == 0) return 9; else if (strcmp("zero", Value) == 0) return 0; else return 0; } int CharsToInt(char * Value)//整体字符串转换为整数值 { int ReturnValue = 0; int i, Pos0 = 0; char LeftNum[10] = {'\0'}; char RightNum[10] = {'\0'}; for(i = 0; i < 100; i++) { if (Value[i] == ' ')//寻找空格的位置 { Pos0 = i; break; } } if (Pos0 > 0)//找到表明是两位数 { strncpy(LeftNum, Value, Pos0); strncpy(RightNum, Value + Pos0 + 1, strlen(Value) - Pos0 - 1); ReturnValue = WordsToInt(LeftNum) * 10 + WordsToInt(RightNum); } else//是一位数 { strcpy(LeftNum, Value); ReturnValue = WordsToInt(strcpy(LeftNum, Value)); } return ReturnValue; } int SumValue(char * Value)//计算机字符串的值 { char LeftValue[100] = {'\0'};//运算式左侧 char RightValue[100] = {'\0'};//运算式右侧 int i, Pos0, Pos1 = 0; for(i = 0; i < 100; i++) { if (Value[i] == '+')//寻找 + 号的位置 { Pos0 = i; } else if (Value[i] == '=')//寻找 = 号的位置 { Pos1 = i; break; } } strncpy(LeftValue, Value, Pos0 - 1);//获取 + 左边的字符串 strncpy(RightValue, Value + Pos0 + 2, Pos1 - Pos0 - 3); //获取 + 右边 与 = 左边 的字符串 return CharsToInt(LeftValue) + CharsToInt(RightValue); }; int main(int argc, char* argv[]) { InPutString * pHeadInPutString = NULL;//首指针 InPutString * pUsedInPutString = NULL;//正在使用的指针 InPutString * pTempInPutString = NULL;//临时使用的指针 char InPut[100]; //输入数据 gets(InPut); while(strcmp(InPut, "zero + zero =") ! = 0)//表明输入数据有效 { pTempInPutString = (InPutString *)malloc(sizeof(InPutString));//申请空间 pTempInPutString->Next = NULL; strcpy(pTempInPutString->Value, InPut); if (NULL == pHeadInPutString)//头指针没有创建 则新建的是头指针 { pHeadInPutString = pTempInPutString; pUsedInPutString = pHeadInPutString; } else//头指针已经创建 则建立的数据放在尾部 { pUsedInPutString->Next = pTempInPutString; pUsedInPutString = pUsedInPutString->Next; } gets(InPut); } //计算数据 //输出数据 pUsedInPutString = pHeadInPutString; while(NULL ! = pUsedInPutString) { printf("%d\n",SumValue(pUsedInPutString->Value)); pTempInPutString = pUsedInPutString; pUsedInPutString = pUsedInPutString->Next; free(pTempInPutString); } return 0; } 位数对调: 输入一个三位自然数,把这个数的百位与个位数对调,输出对 调后的数。 例如: Input 3 bit natrue data: 234 n=432 要求每次输入多组数据(与ACM竞赛类似),输入0时表示输入结束如: 输入为: 123 456 789 0 输出应该为: 321 654 987 [解]1.先确定输入数n 是否三位数,即n>99 且n<=999。 2.位数对调: n=abc→cba=x ①百位数a=n整除100;②十位数b=(n-a*100)整除10;③个位数c=n 除以10的余数; 3.得对调后的数: x=c*100+b*10+a */ #include #include struct NumberNode//结构体 { int NumberValue;//输入的数值 NumberNode * Next;//指向下一个结构体的地址 }; // 在解决复杂问题时 可以采用分函数 将问题化简分步求解。 故建立分函数CalcNumber进行百个位互换 int CalcNumber(int Number)//对三位数进行位调 { //return (Number % 10) * 100 + ((Number - (Number / 100)*100) / 10) * 10 + (Number / 100); return (Number % 10) * 100 + ((Number / 10) % 10) * 10 + (Number / 100); } int main(int argc, char* argv[]) { int InNumber = 0; NumberNode * pNumber = NULL;//链表头指针 NumberNode * pTempNumber = NULL;//用来表示当前指针位置的链表指针 //采用链表输入数据 scanf("%d",&InNumber); while((InNumber ! = 0)&&(InNumber <= 999)&&(InNumber >= 100)) { NumberNode * pTemp;//链表临时指针 指向当前创建的结构体的地址 pTemp = (NumberNode *)malloc(sizeof(NumberNode));//申请空间 pTemp->Next = NULL; pTemp->NumberValue = InNumber; if (pNumber == NULL) {//头指针为空,则将新建立的链表做为头指针 pNumber = pTemp; pTempNumber = pNumber; } else//若不为空,则将新建立的结构体地址加入到链表的尾部 {// 注意赋值的先后性 pTempNumber 是指向链表当前位置的指针 pTempNumber->Next = pTemp; pTempNumber = pTemp; } scanf("%d",&InNumber); } //采用链表输入数据 //对结果运算并输出 while(pNumber ! = NULL) { printf("%d\n",CalcNumber(pNumber->NumberValue)); pTempNumber = pNumber; pNumber = pNumber->Next; free(pTempNumber);//释放申请的空间 此句不能掉 否则会造成内存泄露 } return 0; } 寻找大富翁 Problem Description 信阳市共有n个人,请找出该市的前m个大富翁。 Input 输入包含多组测试用例。 每个用例首先包含2个整数n(0 n为信阳市的人数,m为需要找出的大富翁数,接下来一行输入市内n个人的财富值。 n和m同时为0时表示输入结束。 Output 请输出信阳市前m个大富翁的财产数,财产多的排前面,如果大富翁不足m个,则全部输出,每组输出占一行。 Sample Input 3 1 2 5 -1 5 3 1 2 3 4 5 0 0 Sample Output 5 5 4 3 */ #include #include struct Moneybags//富翁的结构体 { int Value;//富翁的金钱数 Moneybags * Next;//指向下一个富翁结构体的地址 }; struct GroupData//每组测试用例的结构体 { int MoneybagsNumber;//输入的富翁数总个数n int CountMoneybagsNumber;//需要输出的前m个大富翁的数值m Moneybags * MoneybagsLinks;//指向当前的第一个富翁 GroupData * NextGroupData;//指向下一组数据 }; void SortData(GroupData * pHeadGroup)//对数据进行排序 { GroupData * pGroup = NULL;//当时使用的组数据指针 Moneybags * pMoneybagsTemp0 = NULL;//临时使用的富翁数据指针 Moneybags * pMoneybagsTemp1 = NULL;//临时使用的富翁数据指针 pGroup = pHeadGroup; int i, j, MaxValue = 0; while(pGroup ! = NULL)//数据组的循环 { i = pGroup->CountMoneybagsNumber; j = 0; MaxValue = 0; pMoneybagsTemp0 = pGroup->MoneybagsLinks; while(NULL ! = pMoneybagsTemp0)//冒泡排序的循环此处使用冒泡排序 { MaxValue = pMoneybagsTemp0->Value; pMoneybagsTemp1 = pMoneybagsTemp0->Next; while(NULL ! = pMoneybagsTemp1) { if (MaxValue < pMoneybagsTemp1->Value) { MaxValue = pMoneybagsTemp1->Value; pMoneybagsTemp1->Value = pMoneybagsTemp0->Value; pMoneybagsTemp0->Value = MaxValue; } j++; pMoneybagsTemp1 = pMoneybagsTemp1->Next; } pMoneybagsTemp0 = pMoneybagsTemp0->Next; } pGroup = pGroup->NextGroupData; } }; void PrintData(GroupData * pHeadGroup)//对数据进行输出 { GroupData * pGroupTemp = NULL;//临时使用的组数据指针 GroupData * pGroup = NULL;//当时使用的组数据指针 Moneybags * pMoneybagsTemp0 = NULL;//临时使用的富翁数据指针 Moneybags * pMoneybagsTemp1 = NULL;//临时使用的富翁数据指针 pGroup = pHeadGroup; int i, j = 0; while(pGroup ! = NULL) { i = pGroup->CountMoneybagsNumber; j = 0; pMoneybagsTemp0 = pGroup->MoneybagsLinks; while(NULL ! = pMoneybagsTemp0) { if (j < i) printf("%d ", pMoneybagsTemp0->Value); pMoneybagsTemp1 = pMoneybagsTemp0; pMoneybagsTemp0 = pMoneybagsTemp0->Next; free(pMoneybagsTemp1); j++; } printf("\n"); pGroupTemp = pGroup; pGroup = pGroup->NextGroupData; free(pGroupTemp);//释放申请的空间 } }; int main(int argc, char* argv[]) { int n = 0;//输入的富翁个数n的临时变量 int m = 0;//需要输出的富翁个数m的临时变量 GroupData * pGroup = NULL;//当时使用的组数据指针 GroupData * pHeadGroup = NULL;//组数据的头指针 //采用链表输入数据 scanf("%d",&n); scanf("%d",&m); while((0 ! = n)&&(0 ! = m))//n,m都不为0时 { GroupData * pGroupTemp;//链表临时指针 指向当前创建的结构体的地址 pGroupTemp = (GroupData *)malloc(sizeof(GroupData));//申请空间 //赋初值 pGroupTemp->MoneybagsNumber = n; pGroupTemp->CountMoneybagsNumber = m; pGroupTemp->NextGroupData = NULL; pGroupTemp->MoneybagsLinks = NULL; if (NULL == pHeadGroup)//头指针没有创建 则新建的是头指针 { pHeadGroup = pGroupTemp; pGroup = pHeadGroup; } else//头指针已经创建 则建立的数据放在尾部 { pGroup->NextGroupData = pGroupTemp; pGroup = pGroup->NextGroupData; } int i = 0; int MoneyValue = 0; Moneybags * pMoneybags = NULL;//当前正在使用的富翁数据指针 Moneybags * pM
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机 学院 ACM 程序设计 竞赛 题目
![提示](https://static.bingdoc.com/images/bang_tan.gif)