工大在线

标题: 第六届编程大赛试题 [打印本页]

作者: liu19880426 时间: 2008-4-23 07:43
标题: 第六届编程大赛试题

初赛试题
（总分150分）
考生须知：
（1）考生必须注明每道试题所用的语言，无声明的以零分计算。
（2）答案复制到一Word文档中，并以考生的姓名及学号命名该文档保存在桌面。
（3）考试中请遵守考试规则。
1.选择题（20分）
有三个白子和三个黑子如下图布置：
○ ○ ○ . ● ● ●
游戏的目的是用最少的步数将上图中白子和黑子的位置进行交换：
● ● ● . ○ ○ ○
游戏的规则是：(1)一次只能移动一个棋子； (2)棋子可以向空格中移动，也可以跳过一个对方的棋子进入空格，但不能向后跳，也不能跳过两个子。
阅读如下程序：
#include<stdio.h>
int number;
void print(int a[]);
void change(int *n,int *m);
int main()
{
int t[7]={1,1,1,0,2,2,2}; /*初始化数组1：白子 2：黑子 0：空格*/
int i,flag;
print(t);
while(t[0]+t[1]+t[2]!=6||t[4]+t[5]+t[6]!=___(1)___) /*判断游戏是否结束
若还没有完成棋子的交换则继续进行循环*/
{
flag=1; /*flag 为棋子移动一步的标记1：尚未移动棋子 0：已经移动棋子*/
for(i=0;flag&&i<5;i++) /*若白子可以向右跳过黑子，则白子向右跳*/
if(t==1&&t[i+1]==2&&t[i+2]==___(2)___)
{change(&t,&t[i+2]); print(t); flag=0;}
for(i=0;flag&&i<5;i++) /*若黑子可以向左跳过白子，则黑子向左跳*/
if(t==0&&t[i+1]==1&&t[i+2]==2)
{change(&t,&t[i+2]); print(t); flag=0;}
for(i=0;flag&&i<6;i++) /*若向右移动白子不会产生阻塞,则白子向右移动*/
if(t==1&&t[i+1]==0&&(___(3)___))
{change(&t,&t[i+1]); print(t);flag=0;}
for(i=0;flag&&i<6;i++) /*若向左移动黑子不会产生阻塞，则黑子向左移动*/
if(t==0&&t[i+1]==2&&(i==5||t[i-1]!=t[i+2]))
{ change(&t,&t[i+1]); print(t);flag=0;}
}
}
void print(int a[])
{
int i;
printf("No. %2d:.............................\n",number++);
printf(" ");
for(i=0;___(4)___;i++)
printf(" | %c",a==1?'*':(a==2?'@':' '));
printf(" |\n .............................\n\n");
}
void change(int *n,int *m)
{
int term;
term=*n; *n=*m; ___(5)___;
}
从下面的选项中选择你认为正确的填入空格{___(1)__}—{___(5)___}内：
A.*m=term B.i==0||t[i-1]!=t[i+2] C.3 D.6 E.0 F. i==0||t[i+1]!=t[i+2]
G.i<=6
H. i==0||t!=t[i+2]
I.i<=5
J.i<=3
K. term=*m
L.term=*n
作者: liu19880426 时间: 2008-4-23 07:44
2.编写程序实现将任一整数（十进制）转换为二进制形式.（15分）
3.编写程序求13的13次方的最后三位数.（20分）
4.贪婪法是一种不追求最优解，只希望最快得到较为满意解的方法。如平时购物找钱时，为得到的硬币最少，先尽量考虑大币种，然后才考虑下一小币种，此方法可归纳为贪婪法。现有面额5分，2分，1分的硬币，用贪婪法求出找钱方案，使得硬币数最少。（假设全用硬币找钱，硬币总额以分为单位）（25分）
5.一辆卡车违反交通规则，撞人后逃跑。现场有三人目击事件，但都没有记住车号，只记下车号的一些特征。甲说：牌照的前两位数字是相同的；乙说：牌照的后两位数字是相同的，但与前两位不同；丙是数学家，他说：四位的车号刚好是一个整数的平方。请根据以上线索求出车号。（30分）
6.某银行共发行M张储蓄卡，每张储蓄卡拥有唯一的卡号，每天每张储蓄卡至多支持储蓄卡持有者的N笔“存款”或“取款”业务。程序中用数组card[M][N+3]中的每一行存放一张储蓄卡的有关信息，其中：
Card[0]存放第i张卡的卡号；
Card[1]存放第i张卡的余额；
Card[2]存放第i张卡的当日业务实际发生笔数；
Card[3]~card[N+2]存放第i张卡的当日取款的金额，正值代表存款，负值代表取款；
要求：
(1)令M=6，N=5,且定义卡的初始状态为：
long card[M][N+3]={{9801,2000,0,},
               {9812,2000,2,},
               {9753,3000,1,},
               {8750,500,0},
               {9604,2800,3,},
               {8901,5000,5}}
(2)当持卡者输入正确的卡号、存款或取款金额后，程序进行相应的处理；当余额不足时，则不能进行取款业务；若输入了不正确的数据，程序会提示持卡者重新输入；若输入的卡号为负值，银行中止当日业务。（40分）
作者: lichao_2007 时间: 2008-4-23 09:25
[s:31] [s:31] 怎么不早发出来呢～都考完了还！～
作者: bigice803 时间: 2008-4-23 13:10
初赛比赛顺利结束，进入复赛选手名单以及复赛日期见科协出的宣传板！
作者: jack2 时间: 2008-4-25 12:47
机房摆设如此先进哦
作者: baggio 时间: 2008-4-26 19:09
[s:19] [s:19] [s:19]
作者: kingwinter 时间: 2008-4-26 20:04
机房在哪里？[s:37]
作者: liu19880426 时间: 2008-4-26 22:31
E510[s:37]
作者: lichao_2007 时间: 2008-4-27 10:48
呵呵～现在的机房可以随便上网的！呵呵～还是团队式的～
作者: Cole 时间: 2008-4-29 09:38
答案公布[s:30]
作者: liu19880426 时间: 2008-4-29 10:17
1.（1）：C  (2):E  (3):B  (4):G  (5):A
作者: liu19880426 时间: 2008-4-29 10:17
2..(二进制)
#include<stdio.h>
void printb(int,int);
int main()
{
int x;printf("Input number:");
scanf("%d",&x);
printf("number of decimal form:%d\n",x);
printf(" it's binary form:");
printb(x,sizeof(int)*8); /*x:整数 sizeof(int):int型在内存中所占的字节数
sizeof(int)*8:int型对应的位数*/
putchar('\n');
}

void printb(int x,int n)
{
if(n>0)
{
putchar('0'+((unsigned)(x&(1<<(n-1)))>>(n-1))); /*输出第n位*/
printb(x,n-1); /*归调用，输出x的后n-1位*/
}
}
3.
#include<stdio.h>
int main()
{
int i,x,y,last=1; /*变量last保存求X的Y次方过程中的部分乘积的后三位*/
printf("Input X and Y(X**Y):");
scanf("%d**%d",&x,&y);
for(i=1;i<=y;i++) /*X自乘Y次*/
last=last*x%1000; /*将last乘X后对1000取模，即求积的后三位*/
printf("The last 3 digits of %d**%d is:%d\n",x,y,last%1000); /*打印结果*/
}
运行结果：253
作者: liu19880426 时间: 2008-4-29 10:18
4.
#include "stdio.h"
main()
{
  int a[3]={5,2,1};
  int b[3];
  int s;
  int i;
  printf("请输入货币总额: ");
  scanf("%d",&s);
for(i=0;i<=3;i++)
   {
b=s/a;
s-=b*a;
   }
for(i=0;i<3;i++)
printf("面值为%d硬币%d枚\n",a,b);

}
5.（交通违规）
#include<stdio.h>
#include<math.h>
int main()
{
int i,j,k,c;
for(i=1;i<=9;i++) /*i:车号前二位的取值*/
for(j=0;j<=9;j++) /*j:车号后二位的取值*/
if(i!=j) /*判断二位数字是否相异*/
{
k=i*1000+i*100+j*10+j; /*计算出可能的整数*/
for(c=31;c*c<k;c++); /*判断该数是否为另一整数的平方*/
if(c*c==k) printf("Lorry--No. is %d.\n",k); /*若是，打印结果*/
}
}
运行结果：7744
6.
#include<stdio.h>
#define M 6
#define N 5
long card[M][N+3]={
               {9801,2000,0,},
               {9812,2000,2,},
               {9753,3000,1,},
               {8750,500,0},
               {9604,2800,3,},
               {8901,5000,5}
               };
int locate(long card[][N+3],int m,long no)
{int i;
for(i=0;i<m;i++)
if(card[0]=no)return i;
return -1;
}
main()
{
long cardNo,money;
int k;
while(1)
{
   printf("请输入卡号：\n");
scanf("%d",&cardNo);
if(cardNo<0)break;
k=locate(card,M,cardNo);
if(k==-1)
   {
     printf("不存在%d号的储蓄卡\n",cardNo);continue;
   }
printf("请输入卡金额（正值代表存款，负值代表取款）：\n");
scanf("%Ld",&money);
if(card[k][1]+money<0)
   {
      printf("存款余额不足，不能完成本次的取款业务\n");
      continue;
   }
if(card[k][2]==N)
   {
      printf("已完成本卡的当日业务\n");
      continue;
   }
/*处理一笔业务的数据*/
card[k][card[k][2]+3]=money;
card[k][card[k][2]+3]=money;
card[k][2]++;
}
}
作者: lichao_2007 时间: 2008-4-29 14:22
呵呵～
作者: 夜色温柔 时间: 2008-5-1 19:24
初赛？我总觉得我们学校的大赛所出的试题过于简单了，我真心希望有一天我们学校的同学能站在ACM的舞台上，同世界上最优秀的编程爱好者进行面对面的较量。
自己从另一条路实现了下第二题算是为大赛祝兴吧~~~~~~~~
10进制转2进制C++版
#include <vector>
#include<iostream>
using namespace std;
int main(int argc, char *argv[])
{
                  vector<int> o;
int x = 0;
cin>>x;
while(x != 0)
{
if((x&1) == 1)
o.push_back(1);
else
o.push_back(0);
x=x>>1;
}
for(vector<int>::reverse_iterator it = o.rbegin() ; it != o.rend() ; it++  )
      cout<<*it;
system("PAUSE");
return 0;
}
作者: dixnuits 时间: 2008-5-10 17:20

原帖由 夜色温柔 于 2008-5-1 19:24 发表
初赛？我总觉得我们学校的大赛所出的试题过于简单了，我真心希望有一天我们学校的同学能站在ACM的舞台上，同世界上最优秀的编程爱好者进行面对面的较量。
自己从另一条路实现了下第二题算是为大赛祝兴吧~~~~~ ...

用栈实现还是最有效率的.

我现在在用C#,更简单,呵呵
System.Convert.ToString(int value, int toBase)
即可解决问题,任意进制的转换.

[ 本帖最后由 dixnuits 于 2008-5-10 17:23 编辑 ]
作者: liu19880426 时间: 2008-5-10 18:01
初赛？我总觉得我们学校的大赛所出的试题过于简单了，我真心希望有一天我们学校的同学能站在ACM的舞台上，同世界上最优秀的编程爱好者进行面对面的较量。
上面的那位老兄以为你做对了吗？
你错了~
还说简单！
简单的都做不了！
作者: liu19880426 时间: 2008-5-10 18:02
你用你的程序试一下，看负数能表示出来么？

确定后再说，别说大话~~

            OK？
作者: dixnuits 时间: 2008-5-10 19:09
我倒是没事把决赛试题做了做

你可以去看看

我可以告诉你二进制的负数需要说明位数的

int32和int16就完全不同

而且,在C#中转换是包含负数的默认为 Int32
作者: dixnuits 时间: 2008-5-10 19:11
我反倒认为你给的初赛的答案错误百出

用int声明主函数结尾没有返回值,稍微严格一点的编译器就给你编译错误了.

我不是用C的,我现在工作用的python和C#.

但是我还是有C的基本的常识.
作者: dixnuits 时间: 2008-5-10 19:16
这个话题就此打住

我看见那些用火星文的非主流的脑残体

我就觉得恶心
作者: 夜色温柔 时间: 2008-5-10 20:57
嗯看来我疏忽了先把程序改一下
#include <math.h>
#include <vector>
#include <iostream>
using namespace std;
int main(int argc, char *argv[])
{
                  char a[2] = {'+','-'};
                  vector<int> o;
int k = 0,x = 0;
cin>>x;
                     if( x < 0)
k = 1;
x = abs(x);
while(x != 0)
{
if((x&1) == 1)
o.push_back(1);
else
o.push_back(0);
x=x>>1;
}
cout<<a[k];
for(vector<int>::reverse_iterator it = o.rbegin() ; it != o.rend() ; it++  )
cout<<*it;
system("PAUSE");
return 0;
}

liu19880426同学，你激动个啥，难道我们学校这个编程大赛还只准人说好话了，我提供了一种实现思路，没有详细测试，是我的疏

忽。但是我错了就代表我们的大赛水平很高了？你不会真的认为我们学校的水平已经立于世界之巅，无须提高了吧。
作者: 夜色温柔 时间: 2008-5-10 21:06

原帖由 dixnuits 于 2008-5-10 17:20 发表

用栈实现还是最有效率的.

我现在在用C#,更简单,呵呵
System.Convert.ToString(int value, int toBase)
即可解决问题,任意进制的转换.

呵呵，这个其实并非C#专有，在.NET Framework 类库中，其C++语法表示为：
public:static String^ System::Convert::ToString (nt value, int toBase)
程序集:mscorlib（在 mscorlib.dll 中）
作者: bigice803 时间: 2008-5-10 21:25
这里这么热闹呀!
为什么决赛那边没这里热闹?看来决赛的题还是有些难了……
作者: dixnuits 时间: 2008-5-10 21:38

原帖由 夜色温柔 于 2008-5-10 21:06 发表

呵呵，这个其实并非C#专有，在.NET Framework 类库中，其C++语法表示为：
public:static String^ System::Convert::ToString (nt value, int toBase)
程序集:mscorlib（在 mscorlib.dll 中）

恩是.NET类库里的

我对.NET也是初学,类都记不清楚,不停要看MSDN,毕竟不是这个专业.(我现在做网络的)

各种语言都会点,但都不精通.
作者: dixnuits 时间: 2008-5-10 21:38

原帖由 bigice803 于 2008-5-10 21:25 发表
这里这么热闹呀!
为什么决赛那边没这里热闹?看来决赛的题还是有些难了……

决赛的题我做了,今天上班的时候,趁领导不在,偷偷摸摸写的,很乱,但实现功能没问题.
作者: bigice803 时间: 2008-5-14 19:33

原帖由 dixnuits 于 2008-5-10 21:38 发表

决赛的题我做了,今天上班的时候,趁领导不在,偷偷摸摸写的,很乱,但实现功能没问题.

上班这么严呀.对了,现在你在搞网络,做网页吗??是什么网络公司呢?能不能给学弟偷漏下??

欢迎光临工大在线 (http://ruolanmy.hk1.ifreeurl.com/) Powered by Discuz! X2.5