主题：6道编程题(做出一道加10分)
LSQ
[专家分：220] 发布于 2006-05-21 21:14:00
(1)从键盘输入两个自然数N，R（N＞R），要求输出从N到1中按降序顺序取R个自然数的所有组合和个数。
例如： 输入: N＝5，R=3
输出: 543，542，541，532，531，521，432，431，421，321
Total＝10
(2)有3N个花盆，红色、蓝色、黄色各N个，按任意顺序排成一行。编程将各花盆按红、黄、蓝；红、黄、蓝；……红、黄、蓝的顺序排列，且要求花盆之间交换的次数最少。数字1表示红花盆，2表示黄花盆；3表示蓝花盆。要求输出每次交换后的状态和最少交换的次数。
(3)有2N十1个方格，左、右两边各放N个“＋”子和N个“*”子。
例如N=4时，如下图所示：
|+|+|+|+| |*|*|*|*| ' "|"用来分栏," "表示一个空格
试编程打印出用最少步数将上图中的“＋”子和“。”子的位置进行交换的步骤。
移动规则如下：
l）一次只能移动一个棋子；
2）棋子可以向空格中移动，也可以跳过对方的一个棋子进人空格，但不能向后跳，也不能跳过两个棋子。
(4)有N枚硬币，将其按1，2，3，…，N编号排列（N＞2），且正面都朝上。现从硬币2开始把编号为2的倍数的硬币翻一个面，再从硬币3开始把编号为3的倍数的硬币翻一个面，接着从硬币4开始把编号为4的倍数的硬币翻一个面。如此类推。直到最后将N号硬币翻一个面。问最后哪些硬币为正面朝上。编程，当从键盘输人N后，则输出结果是哪些硬币。
(5)某人去书店买书，他选中了六本书，价格分别为A、B、C、D、E、F，但他只带了50元钱。问怎样买法使总钱数最接近50元。A、B、C、D、E、F均由键盘输入。
（6）火车从始发站(称为第1站)开出，在始发站上车的人数为A；然后到达第2站，在第2站有人上、下车，但上、下车的人数相同，因此在第2站开出时（即在到达第3站之前）车上的人数保持为A人。从第3站起（包括第3站）上、下车的人数有一定的规律：上车的人数都是前两站上车人数之和，而下车人数等于上一站上车人数，一直到终点站的前一站（第N-1站），都满足此规律。现给出的条件是：共有N个车站，始发站上车的人数为A，最后一站下车的人数是M（全部下车）。请编程求出从X站开出时车上的人数是多少？输入为：A，N，M和X(N，X均小于23)；输出为：X站开出时车上的人数。
回复列表 （共20个回复）
沙发
if007 [专家分：650] 发布于 2006-05-22 20:50:00
除了第二题,其它几道题都不难,既然你选择了竞赛题,有必要让你磨练下,偶就不说那些解法了.
不过第二题我就有点摸不清了,我的解答是这样的,要最后结果是:1 2 3 1 2 3 1 2 3...
乍一看很容易联想到排序,那么我们只需做的是对输入数据作些手段.可以这样做,由于是三个三个一组,故第二个1就可以相当于4(因为1+3=4), 第三个1就相当于7(1+3+3=7),....依此类推,输出的时侯只需取余就行了.
不过我摸不明白的是它要求交换次数最少,可是关于排序的问题,至今没有能求最少的算法,现在的算法都是要针对一定分布情况的,例如说快速排序是针对无单枝情况时最好的...
板凳
if007 [专家分：650] 发布于 2006-05-22 21:06:00
算了,一并说吧,
第一题在穷举的过程的加多个限制条件.
第三题,如果你不想穷举,那么就要采取每次对每种情况进行策略,刚巧以前解过这题,
#include <iostream.h>
const int Max=11; //数字随你改2N+1
int t[Max];
int count=0;
void Init()
{
for (int i=0; i<Max/2; i++)
{
t[i]=-1;
t[Max-i-1]=1;
}
}
void output()
{
for (int i=0; i<Max; i++)
{
if (t[i]==-1) cout<<"a ";
else if (t[i]==1) cout<<"b ";
else cout<<" ";
}
cout<<endl;
}
void change(int a, int b)
{
int temp=t[a];
t[a]=t[b]; t[b]=temp;
}
int condition()
{
int sum1=0, sum2=0;
for (int i=0; i<Max/2; i++)
{
sum1+=t[i];
sum2+=t[Max-i-1];
}
if ( (sum1 == Max/2) && (sum2 == -sum1))
return 0;
return 1;
}
void a_jump(int &flag)
{
for (int i=0; i<Max-2; i++)
if ( t[i]==-1 && t[i+1]==1 && t[i+2]==0 )
{ change(i,i+2); output(); count++; flag=0;}
}
void b_jump(int &flag)
{
for (int i=0; i<Max-2; i++)
if ( t[i]==0 && t[i+1]==-1 && t[i+2]==1 )
{ change(i,i+2); output(); count++; flag=0;}
}
void a_move(int &flag)
{
for (int i=0; i<Max-1; i++)
if ( t[i]==-1 && t[i+1]==0 && (i==0 || t[i-1]!=t[i+2] ))
{ change(i, i+1); output(); count++; flag=0;}
}
void b_move(int &flag)
{
for (int i=0; i<Max-1; i++)
if ( t[i]==0 && t[i+1]==1 && (i==Max-2 || t[i-1]!=t[i+2] ))
{ change(i, i+1); output(); count++; flag=0;}
}
void fun()
{
Init();
output();
int i, flag;
while( condition() )
{
flag=1;
if (flag) a_jump(flag);
if (flag) b_jump(flag);
if (flag) b_move(flag);
if (flag) a_move(flag);
}
cout<<Max-1<<"个字母时,"<<endl;
cout<<"一共最少需移动"<<count<<"次"<<endl;
}
void main()
{
fun();
}
第四题和第六题模拟其程,第六题在模拟后可采取枚举的方法求解.
第五题用动态规划.
3 楼
moz [专家分：37620] 发布于 2006-05-23 11:37:00
第一题的 n!
组合的个数= ------------------
m! * (n-m)!
4 楼
moz [专家分：37620] 发布于 2006-05-23 12:04:00
第一题是组合问题,可能是题目出得有点疏忽,
这个N超过一位数怎么办?它的最大值是多少?
大于9的时候可以用字符代替,但希望别大于207,
否则要出错了,
input N,R
if N>207 or R>N then end
for i=1 to N
s$=chr$(48+i)+s$
next
s1$=right$(s$,R)
s2$=s1$
do
c=c+1
print s2$,
s2$=nextzh$(s$,s2$)
loop until s2$=s1$
print "Total:"; c
end
function nextzh$(a$,b$)
for i=1 to len(b$)
if instr(1,a$,mid$(b$,i,1))>i then
mid$(b$,1,i)=mid$(a$,instr(1,a$,mid$(b$,i,1))-i,i)
exit for
endif
next
if i>len(b$) then b$=right$(a$,len(b$))
nextzh$=b$
end function
5 楼
moz [专家分：37620] 发布于 2006-05-23 13:10:00
第二题:
defint a-z
randomize timer
n = 25 * rnd + 2
s$ = space$(3 * n)
for i = 1 to 3
for j = 1 to n
do
k = 3 * n * rnd + 1
if k > 3 * n then k = 3 * n
if mid$(s$,k,1)=chr$(32)then mid$(s$,k,1)=chr$(48+i)else k=-1
loop while k = -1
next
next
cls
print s$
for i = 1 to 3 * n
a = val(mid$(s$, i, 1))
if (a mod 3) <> (i mod 3) then
q = q + 1
for j = i + 1 to 3 * n
b = val(mid$(s$, j, 1))
if ((b mod 3) <> (j mod 3)) then
e = j
if (b mod 3) = (i mod 3) then exit for
end if
next
c$ = mid$(s$, e, 1)
mid$(s$, e, 1) = mid$(s$, i, 1)
mid$(s$, i, 1) = c$
print s$
end if
next
print q
6 楼
chenhonghong [专家分：70] 发布于 2006-05-25 16:45:00
靠
QBASIC讨论区你居然用c语言做
这算什么..............................................................
7 楼
lanyuewei [专家分：60] 发布于 2006-05-25 22:19:00
[em15]
8 楼
lanyuewei [专家分：60] 发布于 2006-05-25 22:19:00
可见C语言的势力之大啊
9 楼
if007 [专家分：650] 发布于 2006-05-25 23:07:00
说明一下, 这是C++的,而非C的,C++提供了类机制,而C则还停留在过程化编程,若论效率,C++对大事情来说应该是更有power的,因为过程化编程注重的是细节,而对象化的注重的是整体构局,应该是提高效率的根本之道.
其次,这里提的主要就是思路,语言只是个副件,请不要太动气.
仇'优'心理不是很好,杀'优'提劣解决不了问题,就算杀得了这里的'优',杀得出国外吗? 杀得了全世界的'优'吗? 有好东西就是要用"拿来主义",敢拿敢用天经地义.
10 楼
LSQ [专家分：220] 发布于 2006-05-28 18:00:00
二楼的,请把C语言改写成Qbasic语言,我看不懂
我来回复
您所在位置：