[全民编程]76道高难度C++练习题.含NOI竞赛题.欢迎挑战 - 编程论坛

#152

HJin2007-07-04 11:11

回复：（野比）[全民编程]76道高难度C++练习题.含NOI竞...

/*---------------------------------------------------------------------------
File name: C76-21.cpp
Author: HJin (email: fish_sea_bird[at]yahoo.com)
Created on: 7/3/2007 17:18:43
Environment: Windows XP Professional SP2 English +
Visual Studio 2005 v8.0.50727.762

Modification history:
===========================================================================

Problem statement:
---------------------------------------------------------------------------

经典 76 道编程题之 21:

21. 请设计一个程序，由计算机把1－8的八个自然数填入图中，使得横、
竖、对角任何两个相邻的小方格中的两个数是不连续的。(下图右侧的 4 个图
为禁止的情形).
┌─┐ ┌─┐ ┌─┐
│ │ │4 │ │8 │
┌─┼─┼─┐ └─┼─┐ ┌─┼─┘
│ │ │ │ │5 │ │7 │
├─┼─┼─┤ └─┘ └─┘
│ │ │ │ ┌─┐
└─┼─┼─┘ │6 │ ┌─┬─┐
│ │ ├─┤ │1 │2 │
└─┘ │7 │ └─┴─┘
└─┘

Analysis:
---------------------------------------------------------------------------

Check all neighbors of (i, j) to see if a matrix is valid.

Sample output:
---------------------------------------------------------------------------
(Totally there are four arrangements satisfying the requirements.)

#1
--------------------------------
2
5 8 6
3 1 4
7

#2
--------------------------------
2
6 8 5
4 1 3
7

#3
--------------------------------
7
3 1 4
5 8 6
2

#4
--------------------------------
7
4 1 3
6 8 5
2
Press any key to continue . . .

Reference:
---------------------------------------------------------------------------

1. 野比, [全民编程]76道高难度C++练习题
 https://bbs.bc-cn.net/viewthread.php?tid=147967

*/

#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;

/**
absolute value of a.
*/
inline int abs(int a);

/**
Is it a valid matrix?
*/
bool isValid(int a[][3]);

/**
Do all the neighbors agree with you?
*/
bool checkNeighbors(int a[][3], int i, int j);

/**
copy b[] into a[][].
*/
void copy(int a[][3], int* b);

/**
output results.
*/
void print(int a[][3], int counter, std::ostream& os= cout);

int main(int argc, char** argv)
{
int a[4][3];
int b[8];
int i;
int counter = 0;
ofstream ofs("C76-21-Ans.txt");
if(!ofs)
{
cout<<"cannot open file C76-21-Ans.txt.\n";
exit(0);
}

a[0][0] = -1;
a[0][2] = -1;
a[3][0] = -1;
a[3][2] = -1;

for(i=0; i<8; ++i)
b[i] = i+1;
copy(a, b);
if(isValid(a))
{
++counter;
print(a, counter);
}

while( next_permutation(b, b+8) )
{
copy(a, b);
if(isValid(a))
{
++counter;
print(a, counter);
print(a, counter, ofs);
}

}

ofs.close();

return 0;
}

bool isValid(int a[][3])
{
int i;
int j;

for(i=0; i<4; ++i)
{
for(j=0; j<3; ++j)
{
if( a[i][j] > 0 && (!checkNeighbors(a, i, j)) )
{
return false;
}
}

}

return true;
}

bool checkNeighbors(int a[][3], int i, int j)
{
/**
i \in [0, 3];
j \in [0, 2];

(i,j) can have 3, 5, or 8 neighbors.
*/

if(
( i>=1 && abs(a[i][j] - a[i-1][j]) == 1 ) || /** check (i-1, j) */
( i<=2 && abs(a[i][j] - a[i+1][j]) == 1 ) || /** check (i+1, j) */
( j>=1 && abs(a[i][j] - a[i][j-1]) == 1 ) || /** check (i, j-1) */
( j<=1 && abs(a[i][j] - a[i][j+1]) == 1 ) || /** check (i, j+1) */
( (i>=1 && j>=1) && abs(a[i][j] - a[i-1][j-1]) == 1 ) || /** check (i-1, j-1) */
( (i>=1 && j<=1) && abs(a[i][j] - a[i-1][j+1]) == 1 ) || /** check (i-1, j+1) */
( (i<=2 && j>=1) && abs(a[i][j] - a[i+1][j-1]) == 1 ) || /** check (i+1, j-1) */
( (i<=2 && j<=1) && abs(a[i][j] - a[i+1][j+1]) == 1 ) /** check (i+1, j+1) */
)
{
return false;
}

return true;
}

int abs(int a)
{
return a>=0 ? a: -a;
}

void copy(int a[][3], int* b)
{
a[0][1] = b[0];
a[1][0] = b[1];
a[1][1] = b[2];
a[1][2] = b[3];
a[2][0] = b[4];
a[2][1] = b[5];
a[2][2] = b[6];
a[3][1] = b[7];
}

void print(int a[][3], int counter, std::ostream& os)
{
int i;
int j;

os<<"\n#"<<counter<<endl;
os<<"--------------------------------\n";
for(i=0; i<4; ++i)
{
for(j=0; j<3; ++j)
{
if(a[i][j]>0)
{
os<<a[i][j]<<" ";
}
else
{
os<<" ";
}
}
os<<endl;
}
}

#153

zkkpkk2007-07-04 11:12

回复：（aipb2007）回复：（zkkpkk）临放假前最后一道...

恩，还会来的，去外婆家修养个把星期后

#154

HJin2007-07-04 11:19

回复：（zkkpkk）回复：（aipb2007）回复：（zkkpkk）...

good luck and

make progress in your study.

#155

野比2007-07-04 13:08

Have a nice trip...

#156

zkkpkk2007-07-04 19:20

回复：（HJin）回复：（zkkpkk）回复：（aipb2007）回...

The same to you!

#157

dlcdavid2007-07-05 13:26

呼叫楼猪~~~~~~~~
写个程序把
目前已完成题目(按发帖时间先后排序)
按题号排起

~~

呵呵

#158

野比2007-07-05 14:03

我没时间啊... 你帮我写一个? 谢拉...
要用空格, 不要用制表符啊...

ps... 今年是猪年没错.. .. 和我有啥关系?..

#159

allen303alle2007-07-05 14:29

才发现这个帖子哈，暑假有空做下看，请问这里的人是大学生多还是高中生多啊

这么找NOI的题呢？ACM的似乎更合适哈～～～

#160

smartwind2007-07-05 15:08

31题：
解答说明：
甲只要保证第一次取完后留给乙的棋子数是2的n次方，且大于所取走的棋子数就必胜
因此，如果开始的棋子数是2的n次方，则甲无必胜方法
下面的程序演示了甲的策略，（程序包含了出错处理，所以比较长）

程序代码：

#include <iostream>
using namespace std;

#define MAX 100000

int num(int n,int k=0);

int main()
{
int n,k,m;
cout<<\"请输入不大于\"<<MAX<<\"的正整数，输入0退出\"<<endl;
while(cin>>n&&(n>MAX||n<0))
  cout<<\"请重新输入\"<<endl;
if(n==0)
  goto END;
m=num(n);
if(m<0)
  goto END;
n-=m;
while(n!=0)
{
  cout<<\"我取走\"<<m<<\"\t剩余：\"<<n<<endl<<\"请问你取走多少个？\"<<endl;
  while(cin>>k&&(k>m||k<0||k>n))
   cout<<\"请重新输入\"<<endl;
  if(k==0)
   goto END;
  n-=k;
  cout<<\"你取走\"<<k<<\"\t剩余：\"<<n<<endl;
  if(n==0)
  {
   cout<<\"你胜利了！\"<<endl;
   goto END;
  }
  m=num(n,k);
  if(m<0)
   goto END;
  n-=m;
}
cout<<\"我取走\"<<m<<\"\t剩余：\"<<n<<endl;
cout<<\"你输了\"<<endl;
END:system(\"pause\");
return 0;
}

int num(int n,int k)
{
if(n<=k)
  return n;
int i,t=1;
while(t<=n)
{
  t*=2;
}
t/=2;
if(t==n)
{
  if(k==0)
   cout<<\"非必胜\"<<endl;
  t=n/2-2;
}
else if(k==0)
  cout<<\"必胜\"<<endl;
t=n-t;
if(t>k&&k!=0)
{
  t=1;
  while(t<=k&&n%t==0)
   t*=2;
  t/=2;
}
if(t<1||(k!=0&&t>k)||t>n)
{
  cout<<\"Error:\"<<endl<<n<<\"\t\"<<k<<\"\t\"<<t<<endl;
  return -1;
}
return t;
}

#161

smartwind2007-07-05 15:29

34题简单分析下好了

规则A：
保证留给对方的棋子数为(k+1)*n

规则B：
留下(k+1)*n+1

后拿棋子的就非常被动了

#162

smartwind2007-07-05 17:38

HJin第37题的解答也太复杂了
最大应该是M%N个m/n+1,剩余全部是m/n

#163

HJin2007-07-05 18:18

以下是引用smartwind在2007-7-5 17:38:02的发言：

HJin第37题的解答也太复杂了
最大应该是M%N个m/n+1,剩余全部是m/n

Very good answer. +1

#164

HJin2007-07-05 18:29

以下是引用smartwind在2007-7-5 15:08:19的发言：

31题：
解答说明：
甲只要保证第一次取完后留给乙的棋子数是2的n次方，且大于所取走的棋子数就必胜
因此，如果开始的棋子数是2的n次方，则甲无必胜方法
下面的程序演示了甲的策略，（程序包含了出错处理，所以比较长

I arrived at the idea of 2^n. Another observation is:

If at any given time, A is choosing from odd number of stones, A wins. A simply picks 1 stone at that time.

I did not really read your program,

请输入不大于100000的正整数，输入0退出
16
非必胜
我取走10 剩余：6
请问你取走多少个？
2
你取走2 剩余：4
我取走2 剩余：2
请问你取走多少个？
2
你取走2 剩余：0
你胜利了！
Press any key to continue . . .

but here is my thought: you may simulate the moves of B randomly (still following the rules, though). Or when B is choosing from 2^n or odd number of stones, let B use best strategy.

Good work!

[此贴子已经被作者于2007-7-5 19:00:31编辑过]

#165

smartwind2007-07-06 08:58

if(t==n)
{
  if(k==0)
   cout<<\"非必胜\"<<endl;
  t=n/2-2;       //此处改成+2
}

这样就不会出现拿走超过一半棋子的情况了
或者改成一个随机数

#166

smartwind2007-07-06 09:05

第41题链表规并算法，其余部分zkkpkk已经写了，就不重复了

void link(NODE* p,NODE* q)
{
    NODE* r;
    while(p!=NULL&&q!=NULL)
    {
        r=p->next;
        p->next=q;
        p=r;
        r=q->next;
        if(p!=NULL)
            q->next=p;
        q=r;
    }
}

#167

zkkpkk2007-07-06 09:56

以下是引用smartwind在2007-7-6 9:05:00的发言：
第41题链表规并算法，其余部分zkkpkk已经写了，就不重复了

void link(NODE* p,NODE* q)
{
    NODE* r;
    while(p!=NULL&&q!=NULL)
    {
        r=p->next;
        p->next=q;
        p=r;
        r=q->next;
        if(p!=NULL)
            q->next=p;
        q=r;
    }
}

呵呵，多谢改进，那是我老早以前写的了，现在翻出来的，其实3个指针是够了，但是貌似你忘记了A表，B表不等长时对余出部分的处理，还有我的那个43题多项式的乘法我觉得运算后应该检查合并同类项的我没有做，我要走了，最后一灌，11点左右的车，88！

#168

ichigo2007-07-06 15:00

谁帮我找点简单的题．．．或者从这里边选道简单的．．．

#169

smartwind2007-07-06 16:58

以下是引用zkkpkk在2007-7-6 9:56:18的发言：

呵呵，多谢改进，那是我老早以前写的了，现在翻出来的，其实3个指针是够了，但是貌似你忘记了A表，B表不等长时对余出部分的处理，还有我的那个43题多项式的乘法我觉得运算后应该检查合并同类项的我没有做，我要走了，最后一灌，11点左右的车，88！

已经作了处理

#170

野比2007-07-06 21:06

以下是引用allen303alle在2007-7-5 14:29:28的发言：
才发现这个帖子哈，暑假有空做下看，请问这里的人是大学生多还是高中生多啊

这么找NOI的题呢？ACM的似乎更合适哈～～～

这个嘛...多种原因..
1. 我找到的这份习题就只有NOI的...
2. 考虑到有不少朋友都是才接触C++不久(半年,1年多?).....不要搞那么难
3. 考虑到有不少朋友平时学业, 工作都很忙..没有多少时间.不要搞那么难
4. 考虑到NOI的题比较具体形象..难度又不算太高..开发智力练习编程正好...

欢迎整理一份ACM的题目出来..大家研究研究

#171

野比2007-07-06 21:09

NOI是给中学生的精英中的精英设计的... 正好适合普通大学生
ACM是给大学生的精英中的精英设计的... 正好适合超人大学生

#172

smartwind2007-07-09 17:44

45. (数列的最小代价) 给定一个正整数序列，例如：4,1,2,3, 不改变数的位置把
它们相加，并且由括号来标记每一次加法所得到的和。例如：((4+1)+(2+3))=
((5)+(5))=10. 除去原数4、1、2、3之外，其余都为中间结果，如：5,5,10, 将中
间结果相加，得到：5+5+10=20, 数 20 称为此数列的一个代价。对于另一种算法:
(4+((1+2)+3))=(4+((3+3))=(4+(6))=10, 得到数列的另一个代价为：3+6+10=19.
若给出 N 个数的数列，求出此数列的最小代价。

程序代码：

#include <iostream>
using namespace std;

int *a,**b,**c,n;

void f();

int main()
{
cout<<\"请输入总数N：\"<<endl;
cin>>n;
a=new int[n];
b=new int*[n];
c=new int*[n];
cout<<\"请依次输入\"<<n<<\"个数\"<<endl;
for(int i=0;i<n;i++)
{
  b[i]=new int[n];
  c[i]=new int[n];
  cin>>a[i];
}
for(int i=0;i<n;i++)
{
  for(int j=0;j<n;j++)
  {
   c[i][j]=0;
   i==j?b[i][j]=a[i]:b[i][j]=0;
  }
  cout<<a[i]<<\" \";
}
cout<<endl;
f();
cout<<\"最小代价为：\"<<c[0][n-1]<<endl;
delete a;
for(int i=0;i<n;i++)
{
  delete b[i];
  delete c[i];
}
delete b;
delete c;
system(\"pause\");
return 0;
}

void f()
{
int x;
for(int k=1;k<n;k++)
  for(int i=0;i<n-k;i++)
   b[i][i+k]=b[i][i+k-1]+a[i+k];
for(int k=0;k<n;k++)
  for(int i=0;i<n-k;i++)
   for(int r=0;r<k;r++)
   {
    x=b[i][i+r]+b[i+r+1][i+k]+c[i][i+r]+c[i+r+1][i+k];
    if(x<c[i][i+k]||c[i][i+k]==0)
     c[i][i+k]=x;
   }
}

[此贴子已经被作者于2007-7-9 17:50:02编辑过]

#173

shiwenxiang2007-07-10 13:53

只能看看，解不了题，学艺中！

#174

孤独义侠2007-07-10 22:06

回复：（huozoo）14#includeusing na...

* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

* 0 * 0 * 0 * 0 * 0 * 0 * 0 * 0 * 0 * 0 * 0 * 0 * 0 *
0 * 0 * 0 * 0 * 0 * 0 * 0 * 0 * 0 * 0 * 0 * 0 * 0 * 0
* 0 * 0 * 0 * 0 * 0 * 0 * 0 * 0 * 0 * 0 * 0 * 0 * 0
* 0 * 0 * 0 * 0 * 0 * 0 * 0 * 0 * 0 * 0
Press any key to continue

#175

野比2007-07-11 23:43

What's this?

#176

mingguang012007-07-12 16:53

回复：（野比）[全民编程]76道高难度C++练习题.含NOI竞...

6.3
#include<iostream.h>
#include<iomanip.h>

void main()
{
int i=0,j=0;
int sum=1;
int left,right,up,down;
int a[6][6];
left=0;
right=0;
up=0;
down=1;
for(i=0;i<6;i++)
for(j=0;j<6;j++)
a[i][j]=0;
i=0;
j=0;
while(sum<=36)
{
if(down==1)
{
if(i<6&&a[i][j]==0)
{
a[i][j]=sum;
i++;
sum++;
}
else
{
down=0;
right=1;
i--;
j++;
}
}
else if(right==1)
{
if(j<6&&a[i][j]==0)
{
a[i][j]=sum;
j++;
sum++;
}
else
{
right=0;
up=1;
j--;
i--;
}
}
else if(up==1)
{
if(i>=0&&a[i][j]==0)
{
a[i][j]=sum;
i--;
sum++;
}
else
{
left=1;
up=0;
i++;
j--;
}
}
else if(left==1)
{
if(j>=0&&a[i][j]==0)
{
a[i][j]=sum;
j--;
sum++;
}
else
{
left=0;
down=1;
j++;
i++;
}

}
}
for(i=0;i<6;i++)
{
for(j=0;j<6;j++)
cout<<setw(5)<<a[i][j];
cout<<endl;
}

}

#177

HJin2007-07-13 02:41

回复：（野比）[全民编程]76道高难度C++练习题.含NOI竞...

/*---------------------------------------------------------------------------
File name: C76-14.cpp
Author: HJin (email: fish_sea_bird [at] yahoo [dot] com)
Created on: 7/3/2007 17:18:43
Environment: Windows XP Professional SP2 English +
Visual Studio 2005 v8.0.50727.762

Modification history:
===========================================================================

Problem statement:
---------------------------------------------------------------------------

经典 76 道编程题之 14:

14. 有黑白棋子各有 N 个(分别用＊和Ｏ代替)，按下图方式排列
＊＊＊．．．＊＊＊ＯＯＯ．．．ＯＯＯ
N个黑棋 N个白棋
允许将相邻两个棋子互换位置，最后使队形成黑白交替排列，试编程实现该操作。

Analysis:
---------------------------------------------------------------------------
We are only allowed to swap to adjacent stones. This can be done as follows:

move N+1st white stone to position 2*1 (position 1 is untouched)
N-1 swaps needed;
move N+2nd white stone to position 2*2 (positions 1 to 3 are untouched)
N-2 swaps needed;
move N+3rd white stone to position 2*3 (positions 1 to 5 are untouched)
N-3 swaps needed;
......
move N+(N-1)st white stone to position 2(N-1) (positions 1 to 2*N-3 are untouched)
1 swap needed;

Totally, we need

(N-1) + (N-2) +... + 1 = N*(N-1)/2 swaps.

Sample output:
---------------------------------------------------------------------------
(n=6)

Step #1: * * * * * O * O O O O O
Step #2: * * * * O * * O O O O O
Step #3: * * * O * * * O O O O O
Step #4: * * O * * * * O O O O O
Step #5: * O * * * * * O O O O O
Step #6: * O * * * * O * O O O O
Step #7: * O * * * O * * O O O O
Step #8: * O * * O * * * O O O O
Step #9: * O * O * * * * O O O O
Step #10: * O * O * * * O * O O O
Step #11: * O * O * * O * * O O O
Step #12: * O * O * O * * * O O O
Step #13: * O * O * O * * O * O O
Step #14: * O * O * O * O * * O O
Step #15: * O * O * O * O * O * O

* O * O * O * O * O * O
number of steps is 15.
Press any key to continue . . .

Reference:
---------------------------------------------------------------------------

1. 野比, [全民编程]76道高难度C++练习题
 https://bbs.bc-cn.net/viewthread.php?tid=147967

*/

#include <iostream>
#include <fstream>
using namespace std;

/**
Swap function.
*/
inline void swap(char& a, char &b);

/**
O(n^2) algorithm.
@param n --- number of black stones. Number of Total stones is n+n = 2*n.
@param numSwaps --- reference to keep record of how many steps we used. For this
algo, the number is n*(n-1)/2 = combination(n, 2).
@param showIntermediateSteps --- do you want to show intermediate steps?
Yes = show it,
No = don't show it.
@param os --- output stream. It defaults to stdout.
*/
void exchange(int n, int& numSwaps,
bool showIntermediateSteps = true,
std::ostream& os = cout);

int main()
{
int n=6;
int numSwaps;
std::ofstream ofs("C76-14-Answer.txt");
if(!ofs)
{
cout<<"cannot open file C76-14-Answer.txt.\n";
exit(0);
}

exchange(6, numSwaps);
exchange(6, numSwaps, true, ofs);

cout<<"number of steps is "<<numSwaps<<"."<<endl;

ofs.close();
return 0;
}

void swap(char& a, char &b)
{
char temp =a;
a = b;
b = temp;
}

void exchange(int n, int& numSwaps,
bool showIntermediateSteps,
std::ostream& os)
{
char *a = new char[2*n];
int i;
int j;
int k;
numSwaps = 0;

for(i=0; i<n; ++i)
{
a[i] = '*';
}
for(i=n; i<2*n; ++i)
{
a[i] = 'O';
}

for(i=0; i<=n-2; ++i)
{
for(j=n+i; j>=2*(i+1); --j)
{
swap(a[j], a[j-1]);
++numSwaps;

if(showIntermediateSteps)
{
os<<"Step #"<<numSwaps<<":\t";
for(k=0; k<2*n; ++k)
{
os<<a[k]<<" ";
}
os<<endl;
}
}
}

// show final result
os<<endl;
for(k=0; k<2*n; ++k)
{
os<<a[k]<<" ";
}
os<<endl;

delete [] a;
}

#178

mingguang012007-07-13 16:48

回复：（野比）[全民编程]76道高难度C++练习题.含NOI竞...

10
#include<iostream.h>
void main()
{
int i,m,n;
int totalnum=0;
int area=0;
cout<<"输入正方形的边长n";
cin>>n;
m=n;
for(i=1;i<=n;i++)
{
int ii;
ii=i*i;
totalnum+=ii;
area+=ii*m;
m--;
}
cout<<"正方形总个数是:"<<totalnum<<endl;
cout<<"所有正方形的总面积："<<area<<endl;

}

#179

HJin2007-07-15 04:27

回复：（野比）[全民编程]76道高难度C++练习题.含NOI竞...

/*---------------------------------------------------------------------------
File name: C76-18.cpp
Author: HJin (email: fish_sea_bird [at] yahoo [dot] com)
Created on: 7/3/2007 17:18:43
Environment: Windows XP Professional SP2 English +
Visual Studio 2005 v8.0.50727.762

Modification history:
===========================================================================

Problem statement:
---------------------------------------------------------------------------

经典 76 道编程题之 18:

18. 在一线性七个格位置的图上有两种不同颜色的棋子 A，B. 排列如下图所示，中间
格的位置为空。
┎─┰─┰─┰─┰─┰─┰─┒
┃A ┃A ┃ A┃ ┃B ┃B ┃B ┃
┖─┸─┸─┸─┸─┸─┸─┚
要求将 A，B 的现行位置交换,形成下图中的排列：
┎─┰─┰─┰─┰─┰─┰─┒
┃B ┃B ┃B ┃ ┃A ┃A ┃A ┃
┖─┸─┸─┸─┸─┸─┸─┚
移动棋子的条件：
(1) 每个格中只准放一个棋子。
(2) 任意一个棋子均可移动一格放入空格内。(You can move both forward and backward.)
(3) 一方的棋子均可跳过另一方的一个棋子进入空格。
(4) 任何棋子不得跳跃两个或两个以上棋子(无论颜色同异)
(5) 任何一个颜色棋子只能向前跳，不准向后跳。(You can only leap forward.)
编程完成有关的移动，并且完成具有2N＋1个格子的情形. 其中两种颜色各有
N个棋子,且中间为空格.

Analysis:
---------------------------------------------------------------------------
Move 1st B to the front, then move the blank back to 2nd B;
Move 2nd B to the next front, then move the blank back to 3rd B;
...
Repeat until we are done.

This algorithm needs 3*n^2 number of moves, where n is the number of
B stones. I think the algorithm is optimal, I don't prove it though.

Sample output:
---------------------------------------------------------------------------
Step #0: AAAAA BBBBB
Step #1: AAAAAB BBBB
Step #2: AAAA BABBBB
Step #3: AAAAB ABBBB
Step #4: AAA BAABBBB
Step #5: AAAB AABBBB
Step #6: AA BAAABBBB
Step #7: AAB AAABBBB
Step #8: A BAAAABBBB
Step #9: AB AAAABBBB
Step #10: BAAAAABBBB
Step #11: B AAAAABBBB
Step #12: BA AAAABBBB
Step #13: BAA AAABBBB
Step #14: BAAA AABBBB
Step #15: BAAAA ABBBB
Step #16: BAAAAA BBBB
Step #17: BAAAAAB BBB
Step #18: BAAAA BABBB
Step #19: BAAAAB ABBB
Step #20: BAAA BAABBB
Step #21: BAAAB AABBB
Step #22: BAA BAAABBB
Step #23: BAAB AAABBB
Step #24: BA BAAAABBB
Step #25: BAB AAAABBB
Step #26: B BAAAAABBB
Step #27: BB AAAAABBB
Step #28: BBA AAAABBB
Step #29: BBAA AAABBB
Step #30: BBAAA AABBB
Step #31: BBAAAA ABBB
Step #32: BBAAAAA BBB
Step #33: BBAAAAAB BB
Step #34: BBAAAA BABB
Step #35: BBAAAAB ABB
Step #36: BBAAA BAABB
Step #37: BBAAAB AABB
Step #38: BBAA BAAABB
Step #39: BBAAB AAABB
Step #40: BBA BAAAABB
Step #41: BBAB AAAABB
Step #42: BB BAAAAABB
Step #43: BBB AAAAABB
Step #44: BBBA AAAABB
Step #45: BBBAA AAABB
Step #46: BBBAAA AABB
Step #47: BBBAAAA ABB
Step #48: BBBAAAAA BB
Step #49: BBBAAAAAB B
Step #50: BBBAAAA BAB
Step #51: BBBAAAAB AB
Step #52: BBBAAA BAAB
Step #53: BBBAAAB AAB
Step #54: BBBAA BAAAB
Step #55: BBBAAB AAAB
Step #56: BBBA BAAAAB
Step #57: BBBAB AAAAB
Step #58: BBB BAAAAAB
Step #59: BBBB AAAAAB
Step #60: BBBBA AAAAB
Step #61: BBBBAA AAAB
Step #62: BBBBAAA AAB
Step #63: BBBBAAAA AB
Step #64: BBBBAAAAA B
Step #65: BBBBAAAAAB
Step #66: BBBBAAAA BA
Step #67: BBBBAAAAB A
Step #68: BBBBAAA BAA
Step #69: BBBBAAAB AA
Step #70: BBBBAA BAAA
Step #71: BBBBAAB AAA
Step #72: BBBBA BAAAA
Step #73: BBBBAB AAAA
Step #74: BBBB BAAAAA
Step #75: BBBBB AAAAA

n # of steps 3*n^2
----------------------------------
1 3 3
2 12 12
3 27 27
4 48 48
5 75 75
6 108 108
7 147 147
8 192 192
9 243 243
10 300 300
11 363 363
12 432 432
13 507 507
14 588 588
15 675 675
16 768 768
17 867 867
18 972 972
19 1083 1083
20 1200 1200
21 1323 1323
22 1452 1452
23 1587 1587
24 1728 1728
25 1875 1875
26 2028 2028
27 2187 2187
28 2352 2352
29 2523 2523
30 2700 2700
31 2883 2883
32 3072 3072
33 3267 3267
34 3468 3468
35 3675 3675
36 3888 3888
37 4107 4107
38 4332 4332
39 4563 4563
Press any key to continue . . .

Reference:
---------------------------------------------------------------------------

1. 野比, [全民编程]76道高难度C++练习题
 https://bbs.bc-cn.net/viewthread.php?tid=147967

*/

#include <iostream>
#include <iomanip>
using namespace std;

char* a; // 1d buffer
int n; // number of A stones

void swap(char&a, char&b);
/**
Move stone B to the front. Note that the front is incrementing.
*/
void moveBToFront(int front, int& counter, bool bShowSteps = true);

/**
Move the blank so that it is directly before next B.
*/
void moveBlank(int front, int& counter, bool bShowSteps = true);

/**
Simulate the moves.
@param bShowSteps = true means we show all the steps,
= false means we show no steps.
*/
int play(bool bShowSteps = true);

/**
Print the buffer.
*/
void print(int counter);

int main()
{
// test #1
n = 5;
play();

// test #2
cout<<"\n\nn # of steps 3*n^2\n";
cout<<"----------------------------------\n";
for(n=1; n<40; ++n)
{
cout<<setw(4)<<std::left<<n<<setw(12)<<play(false)<<3*n*n<<endl;
}

return 0;
}

void swap(char&a, char&b)
{
char temp = a;
a = b;
b = temp;
}

void print(int counter)
{
cout<<"Step #"<<counter<<":\t";
for(int i=0; i<=2*n; ++i)
{
cout<<a[i];
}
cout<<endl;
}

int play(bool bShowSteps)
{
int j;
int counter = 0;
int front = 0;

// fill in the initial status of the stones
a = new char[2*n+1];
for(j=0; j<n; ++j)
{
a[j] = 'A';
}
a[n] = ' ';
for(j=n+1; j<=2*n; ++j)
{
a[j] = 'B';
}
if(bShowSteps)
{
print(counter);
}

while(front<n-1)
{
// move B to front
moveBToFront(front, counter, bShowSteps);
// move the blank before next B
moveBlank(front+1, counter, bShowSteps);

++front; // update front
}

// The blank is before last B, so we need to
// move last B to front.
moveBToFront(front, counter, bShowSteps);

// free memory
delete [] a;

return counter;
}

void moveBToFront(int front, int& counter, bool bShowSteps)
{
char temp;
int j = n +front;

while(j>front)
{
// move B to the blank (backwards)
temp = a[j+1];
a[j+1] = ' ';
a[j] = temp;
++counter;

if(bShowSteps)
{
print(counter);
}

// leap A to the blank (forward)
a[j+1] = a[j-1];
a[j-1] = ' ';
++counter;

if(bShowSteps)
{
print(counter);
}

--j;
}

// one more time --- move B to front
temp = a[j+1];
a[j+1] = ' ';
a[j] = temp;
++counter;

if(bShowSteps)
{
print(counter);
}
}

void moveBlank(int front, int& counter, bool bShowSteps)
{
char temp;
int j = front;

// move the blank so that it is direclty before next B
while(j<n+front)
{
// move the blank forward
temp = a[j+1];
a[j+1] = ' ';
a[j] = temp;
++counter;

if(bShowSteps)
{
print(counter);
}

++j;
}
}

[此贴子已经被作者于2007-7-15 6:48:53编辑过]

#180

HJin2007-07-15 12:22

回复：（野比）[全民编程]76道高难度C++练习题.含NOI竞...

/*---------------------------------------------------------------------------
File name: C76-33.cpp
Author: HJin (email: fish_sea_bird [at] yahoo [dot] com)
Created on: 7/3/2007 17:18:43
Environment: Windows XP Professional SP2 English +
Visual Studio 2005 v8.0.50727.762

Modification history:
===========================================================================

Problem statement:
---------------------------------------------------------------------------

经典 76 道编程题之 33:

33. ( 野人与传教士 ) 设有三个传教士和三个野人来到河边，打算乘一只船从右
岸渡到左岸去。该船最大负载能力为两人，在任何时候，如果野人人数超过传教士
人数，那么野人就会把传教士吃掉。他们怎样才能用这条船安全地把所有人都渡过
河去呢？

Analysis:
---------------------------------------------------------------------------
c --- 传教士
y --- 野人

r --- right bank
l --- left bank
b --- boat

The first time we have 1 c and 1 y on the boat and drop the y, let the c come
back to pick up another y;
from 2nd time, 1 y is always on the boat (i.e., either 1y 1c on the boat or 2y
on the boat) and let y do the transfer job.
...
Repeat until all is done. (the last few steps are a little bit different.)

Totally times to use the boat is 4*n-3.

Sample output:
---------------------------------------------------------------------------
Please input number of barbarians n (n>0): 7
# right bank boat left bank
-------------------------------------------------
0 c (7), y (7)
1 c (6), y (6) cy-->
2 c (6), y (6) <--c* y (1)
3 c (6), y (5) cy--> y (1)
4 c (6), y (5) <--y* c (1), y (1)
5 c (5), y (5) cy--> c (1), y (1)
6 c (5), y (5) <--y* c (2), y (1)
7 c (5), y (4) cy--> c (1), y (2)
8 c (5), y (4) <--y* c (2), y (2)
9 c (4), y (4) cy--> c (2), y (2)
10 c (4), y (4) <--y* c (3), y (2)
11 c (4), y (3) cy--> c (2), y (3)
12 c (4), y (3) <--y* c (3), y (3)
13 c (3), y (3) cy--> c (3), y (3)
14 c (3), y (3) <--y* c (4), y (3)
15 c (3), y (2) cy--> c (3), y (4)
16 c (3), y (2) <--y* c (4), y (4)
17 c (2), y (2) cy--> c (4), y (4)
18 c (2), y (2) <--y* c (5), y (4)
19 c (2), y (1) cy--> c (4), y (5)
20 c (2), y (1) <--y* c (5), y (5)
21 c (1), y (1) cy--> c (5), y (5)
22 c (1), y (1) <--y* c (6), y (5)
23 y (1) yc--> c (6), y (5)
24 y (1) <--y* c (7), y (5)
25 yy--> c (7), y (5)
26 c (7), y (7)
Press any key to continue . . .

Reference:
---------------------------------------------------------------------------

1. 野比, [全民编程]76道高难度C++练习题
 https://bbs.bc-cn.net/viewthread.php?tid=147967

*/

#include <iostream>
#include <string>
#include <iomanip>
#include <sstream>

using namespace std;

/**
The travel plan.

-->yc going from right bank to left bank
(1 y and 1 c are on the boat)
<--y* going from right bank to left bank
(1 y is on the boat, another seat on the boat is empty.
* --- represents an empty seat.)

@param n --- number of 野人

Totally, we need to use the boat 4*n-3 times, n>=1.
*/
int travel(int n);

/**
Print the status of right bank, boat, and the left left bank.
@param rc --- number of 传教士 on right bank
@param ry --- number of 野人 on right bank
@param b --- tells you who is on the boat
@param lc --- number of 传教士 on left bank
@param ly --- number of 野人 on left bank
*/
void print(int rc, int ry, string b, int lc, int ly, int counter);

int main()
{
int n;
cout<<"Please input number of barbarians n (n>0): ";
cin>>n;

travel(n);

return 0;
}

int travel(int n)
{
int rc = n;
int ry = n;
string b;
int lc = 0;
int ly = 0;

int i;
int counter = 0;

string rightBank;
string leftBank;
stringstream oss;

cout<<"# right bank boat left bank\n";
cout<<"-------------------------------------------------\n";
print(rc, ry, " ", lc, ly, counter);

if(n==1) // n = 1 is a special case
{
++counter;
print(0, 0, "cy-->", 0, 0, counter);
++counter;
print(n-1, n-1, " ", 1, 1, counter);

return 1;
}

// first few steps
++counter;
print(n-1, n-1, "cy-->", 0, 0, counter);
++counter;
print(n-1, n-1, "<--c*", 0, 1, counter);

// middle steps
for(i=1; i<=n-2; ++i)
{
++counter;
print(n-i, n-i-1, "cy-->", i-1, i, counter);
++counter;
print(n-i, n-i-1, "<--y*", i, i, counter);
++counter;
print(n-i-1, n-i-1, "cy-->", i, i, counter);
++counter;
print(n-i-1, n-i-1, "<--y*", i+1, i, counter);
}

// final steps
++counter;
print(0, 1, "yc-->", n-1, n-2, counter);
++counter;
print(0, 1, "<--y*", n, n-2, counter);
++counter;
print(0, 0, "yy-->", n, n-2, counter);
++counter;
print(0, 0, " ", n, n, counter);

return counter-1;
}

void print(int rc, int ry, string b, int lc, int ly, int counter)
{
ostringstream oss;
string rightBank;
string leftBank;

cout<<std::left<<setw(4)<<counter<<setw(20);

if(rc >0)
{
oss<<"c (";
oss<<rc;
oss<<"), ";
}

if(ry > 0)
{
oss<<"y (";
oss<<ry;
oss<<")";
rightBank = oss.str();
cout<<rightBank;
}

if(ry + rc == 0)
{
cout<<" ";
}

cout<<setw(7)<<b;

oss.str("");

if(lc >0)
{
oss<<"c (";
oss<<lc;
oss<<"), ";
}

if(ly > 0)
{
oss<<"y (";
oss<<ly;
oss<<")";
leftBank = oss.str();
cout<<leftBank;
}

cout<<endl;
}

#181

HJin2007-07-15 14:09

...
delete a;
for(int i=0;i<n;i++)
{
delete b[i];
delete c[i];
}
delete b;
delete c;
...
void f()
{
...
for(int k=0;k<n;k++)
for(int i=0;i<n-k;i++)
for(int r=0;r<k;r++)
{
...
}
}

very nicely done, bro.

1. You code has bugs for allocating/deallocating --- use delete []
instead of delete for arrays;
2. Your algorithm is a dynamic programming scheme and has O(n^3)
time complexity.

I am thinking about this can be done use a greedy algorithm with O(n^2)
time complexity.

3. It would be better if your soln provided the optimal soln --- this
means you need to track back where the parentheses are put.

[此贴子已经被作者于2007-7-15 14:45:27编辑过]

#182

pboyin2007-07-15 19:30

好难哦，高手们做出来，可不可以贴出来啊

#183

zl_breeze2007-07-15 22:41

回复：（野比）[全民编程]76道高难度C++练习题.含NOI竞...

// 第一题，用递归做

#include<iostream>
using namespace std;

int number[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }, result[ 10 ], n1, n2, n3;
bool used[ 10 ] = { 0 };
void Find( int i );
void print();

int main()
{
Find( 0 );
return 0;
}

void Find( int i )
{
if( i == 10 )
{
n1 = result[ 0 ] * 10000 + result[ 1 ] * 1000 + result[ 2 ] * 100 + result[ 3 ] * 10 + result[ 4 ];
n2 = result[ 3 ] * 100 + result[ 5 ] * 10 + result[ 6 ];
n3 = result[ 7 ] * 10000 + result[ 8 ] * 1000 + result[ 9 ] * 100 + result[ 3 ] * 10 + result[ 4 ];
if( n1 + 2 * n2 == n3 )
print();
}
else{
for(int k = 0; k < 10; k++ )
{
if(!used[k])
{
used[k]=true;
result[i]=number[k];
Find(i+1);
used[k]=false;
}
}
}
}

void print()
{
cout << "\t" << result[ 0 ] << result[ 1 ] << result[ 2 ] << result[ 3 ] << result[ 4 ] << endl;
cout << "\t" << " " << " " << result[ 3 ] << result[ 5 ] << result[ 6 ] << endl;
cout << "+\t" << " " << " " << result[ 3 ] << result[ 5 ] << result[ 6 ] << endl;
cout << "----------------------" << endl;
cout << "\t" << result[ 7 ] << result[ 8 ] << result[ 9 ] << result[ 3 ] << result[ 4 ] << endl;
}

结果：
29786
850
+ 850
------------
31486

[此贴子已经被作者于2007-7-15 22:52:30编辑过]

#184

zl_breeze2007-07-15 23:11

回复：（野比）[全民编程]76道高难度C++练习题.含NOI竞...

//第二题，借用二进制来解题
#include< iostream>

using namespace std;

void main()
{
int A, B, C, D, E;
for( int i = 0; i < 32; i++ )
{
A = ( i & 16 ) >> 4;
B = ( i & 8 ) >> 3;
C = ( i & 4 ) >> 2;
D = ( i & 2 ) >> 1;
E = i & 1;
if( A == 1 && B != 1 )
continue;
if( ( B == 1 && C == 1 ) || ( B == 0 && C == 0 ) )
continue;
if( ( C == 1 && D == 0 ) || ( C == 0 && D == 1 ) )
continue;
if( D == 0 && E == 0 )
continue;
if( E == 1 && !( A == 1 && D == 1 ) )
continue;
if( A == 1 )
cout << "A ";
if( B == 1 )
cout << "B ";
if( C == 1 )
cout << "C ";
if( D == 1 )
cout << "D ";
if( E == 1 )
cout << "E";
}
}

程序输出参加了的人，为：C和D。

#185

HJin2007-07-16 23:43

回复：（野比）[全民编程]76道高难度C++练习题.含NOI竞...

/*---------------------------------------------------------------------------
File name: C76-45.cpp
Author: HJin (email: fish_sea_bird [at] yahoo [dot] com)
Created on: 7/3/2007 17:18:43
Environment: Windows XP Professional SP2 English +
Visual Studio 2005 v8.0.50727.762

Modification history:
===========================================================================

Problem statement:
---------------------------------------------------------------------------
经典 76 道编程题之 45:

45. (数列的最小代价) 给定一个正整数序列，例如：4,1,2,3, 不改变数的位置把
它们相加，并且由括号来标记每一次加法所得到的和。例如：((4+1)+(2+3))=
((5)+(5))=10. 除去原数4、1、2、3之外，其余都为中间结果，如：5,5,10, 将中
间结果相加，得到：5+5+10=20, 数 20 称为此数列的一个代价。对于另一种算法:
(4+((1+2)+3))=(4+((3+3))=(4+(6))=10, 得到数列的另一个代价为：3+6+10=19.
若给出 N 个数的数列，求出此数列的最小代价。

Analysis:
---------------------------------------------------------------------------
The minimum sequence price (SMP) problem:

For n numbers a_1 ... a_n, we need to do n-1 additions, thus there are
n-1 intermediate results. Our goal is to make the sum of these n-1
intermediate results as small as possible.

Let P_{i..j} be the sub-problem for a_i ... a_j, 1<=i <=j <=n, and m[i, j]
the corresponding minimum price. Then

m[i, j] = 0, if i=j; (1)
= min_{i<=k<j} { m[i, k], m[k+1, j]} + (a_i + ... + a_j)
if i<j.

Note that the formula (1) is very similar to the matrix chain order problem
introduced on CLRS [2]'s book.

m[1, n] gives the minimum price for a_1 .... a_n. To track back where we should
put the parentheses, we use another matrix to keep record of the k which minimizes
the equation in (1).

Sample output:
---------------------------------------------------------------------------
Optimal solution is:
(4+((1+2)+3))
Minimum sequence price is 19.
Press any key to continue . . .

Optimal solution is:
(((((1+2)+3)+(4+5))+(6+7))+((8+9)+10))
Minimum sequence price is 173.
Press any key to continue . . .

Optimal solution is:
(((1+-2)+(9+-3))+10)
Minimum sequence price is 25.
Press any key to continue . . .

Reference:
---------------------------------------------------------------------------

1. 野比, [全民编程]76道高难度C++练习题
 https://bbs.bc-cn.net/viewthread.php?tid=147967

2. CLRS, introduction to algorithms, 2nd ed, MIT press.

*/

#include <iostream>
using namespace std;

#define INFPos (~(1<<31))
#define DIM(a) sizeof( (a) ) / sizeof ( (a)[0] )

/** Implement formula (1).

O(n^3) time + O(n^2) space.
*/
int smp(int*a, int n);

/**
Print the optimal solutions (the parentheses) recursively.
*/
void printOptSoln(int**s, int*a, int i, int j);

template <class T>
T** new2dInit(int row, int col)
{
T** arr2d = new T*[row];
int i;
int j;

for(i=0; i<row; ++i)
{
arr2d[i] = new T[col];
}

for(i=0; i<row; ++i)
{
for(j=0; j<col; ++j)
{
arr2d[i][j] = T();
}
}

return arr2d;
}

template <class T>
void delete2d(T** arr2d, int row)
{
for(int i=0; i<row; ++i)
{
delete [] arr2d[i];
}

delete [] arr2d;
}

int main()
{
// test #1
int a[] = {4, 1, 2, 3};
smp(a, DIM(a));

// test #2
//int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
//smp(a, DIM(a));

// test #3 --- numbers can be negative
//int a[] = {1, -2, 9, -3, 10};
//smp(a, DIM(a));

return 0;
}

int smp(int*a, int n)
{
int** m;
int** s;

int i;
int j;
int k;
int l; // length of a subproblem P_{i..j}
int q;
int sum; // a_i + ... + a_j

m = new2dInit<int>(n, n);
s = new2dInit<int>(n, n);

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

// assign m[i,j] to be \+inf
m[i][j] = INFPos;

/**
This sum has been repeatedly calculated.

You could use another 2d buffer to store the
results. The situation is that we have two choices here:

choice #1: 3n^2 space + n^3 time (allocate a new 2d buffer for the sums)
choice #2: 2n^2 space + 2n^3 time.

As implemented, we are using choice #2.
*/
sum = 0;
for (k=i; k<=j; ++k)
{
sum += a[k];
}

for (k=i; k<j; ++k)
{
// implement (1)
q = m[i][k] + m[k+1][j] + sum;
if ( m[i][j] > q )
{
m[i][j] = q;
s[i][j] = k;
}
}
}
}

cout<<"Optimal solution is:\n";
printOptSoln(s, a, 0, n-1);

j = m[0][n-1]; // reuse j to keep m[0][n-1]

cout<<"\nMinimum sequence price is "<<j<<"."<<endl;

// free memory
delete2d<int>(m, n);
delete2d<int>(s, n);

return j;
}

void printOptSoln(int** s, int*a, int i, int j)
{
if(i==j)
{
cout<<a[i];
}
else
{
cout<<"(";
printOptSoln(s, a, i, s[i][j]); // i..k
cout<<"+";
printOptSoln(s, a, s[i][j]+1, j); // k+1..j
cout<<")";
}
}

#186

zl_breeze2007-07-17 10:29

回复：（野比）[全民编程]76道高难度C++练习题.含NOI竞...

//第三题
#include<iostream>

using namespace std;

int main()
{
int n;
cout << "Input the number N, and you must make sure that N is between 3 and 20:\n";
cin >> n;
if( n < 4 || n > 19 )
cout << "Input Error!!\n";
else {
for ( int i = 0; i < n; i ++ )
{
for ( int j = 0; j < n; j ++ )
{
if( j == 0 || i == 0 || n - j == 1 || n - i == 1 )
cout << "T";
else if( j == 1 || i == 1 || n - j == 2 || n - i == 2 )
cout << "J";
else if( i < n / 2 && i - j > 0 )
cout << j - 1;
else if( i < n / 2 && i - j < 0 && j - i > n - 2 - 2 * i )
cout << n - j - 2;
else if( i < n / 2 )
cout << i - 1;
else if( i >= n / 2 && i > j && j < n - 1 - i )
cout << j - 1;
else if( i >= n / 2 && i < j )
cout << n - 2 - j;
else cout << n - 2 - i;
}
cout << endl;
}
}
return 0;
}

#187

zl_breeze2007-07-17 10:47

回复：（zl_breeze）回复：（野比）[全民编程]76道高难...

//第五题
#include <iostream>
#include <string>
using namespace std;

int main()
{
int num, n, temp;
string res, mid;
mid = " ";
cout << "输入要转换的数：\n";
cin >> num;
cout << "你要把它转换成几进制？\n";
cin >> n;
while( num )
{
temp = num % n;
num /= n;
if( temp < 10 )
mid[ 0 ] = '0' + temp;
else mid[ 0 ] = 'A' + temp - 10;
res = mid + res;
}
cout << res << endl;
return 0;
}

[此贴子已经被作者于2007-7-17 10:47:58编辑过]

#188

zl_breeze2007-07-17 10:59

//第四题
#include <iostream>
using namespace std;

int main()
{
int *arr, n;
cout << "你要想打印几阶方正？\n";
cin >> n;
arr = new int[ n ];
for( int i = 0; i < n; i++ )
arr[ i ] = i + 1;
for( int j = 0; j < n; j++ )
{
int k = j;
while( true )
{
cout << arr[ k ] << " ";
k ++;
if( k == n )
k = 0;
if( k == j )
break;
}
cout << endl;
}
return 0;
}

[此贴子已经被作者于2007-7-17 10:59:22编辑过]

#189

xinghuo2007-07-17 12:49

７６道完整版有答案没？

#190

げ訾澐み2007-07-18 09:32

看看

#191

youniankang2007-07-18 20:03

给我发个Visual C++ 6.0 中文版的谢谢了我的电子邮箱是
youniankang@163.com

#192

jianweichief2007-07-18 20:42

回复：（kai）关于第一题给出另一种解法：ABCDE + (DF...

如果"且不同数字对应不同字母"这句话可以这么理解的话（a!=b!=c!=d!=e!=f!=g!=x!=y!=z）那么，f必为5或0而g必为0。则可以省去一些不步骤。

#193

zhchchqihu2007-07-20 15:31

2. Ａ、Ｂ、Ｃ、Ｄ、Ｅ五名学生有可能参加计算机竞赛，根据下列条件判断哪些
人参加了竞赛：

（１）Ａ参加时，Ｂ也参加；

（２）Ｂ和Ｃ只有一个人参加；

（３）Ｃ和Ｄ或者都参加，或者都不参加；

（４）Ｄ和Ｅ中至少有一个人参加；

（５）如果Ｅ参加，那么Ａ和Ｄ也都参加。

-----------------------------------------------------------------------------------------------------
我也来发表一下我的做法:
include <iostream>
using namespace std;
int main()
{
int part[2]={'不参加','参加'];//part[0]表示不参加,part[1]表示参加
for(int A=0;A<=1;A++)//A、B\C\D分别控制在１或０
for(int B=0;B<=1;B++)
for(int c=0;C<=1;C++)
for(int D=0;D<=1;D++)
if(A&&B==1)&&(B||C==1)&&(C&&D==1||C&&D==0)&&(D||E==1)&&(E&&A&&D==1)
{ cout<<part[A]<<" "<<part[b]<<" "<<part[C]<<" "<<part[D]<<endl;
}
return 0;
}
由于我是在网吧编的,没有编译环境,不知道语法对不对,如果有不明白的加我的QQ:12814441

#194

zhchchqihu2007-07-20 18:40

2. Ａ、Ｂ、Ｃ、Ｄ、Ｅ五名学生有可能参加计算机竞赛，根据下列条件判断哪些
人参加了竞赛：

（１）Ａ参加时，Ｂ也参加；

（２）Ｂ和Ｃ只有一个人参加；

（３）Ｃ和Ｄ或者都参加，或者都不参加；

（４）Ｄ和Ｅ中至少有一个人参加；

（５）如果Ｅ参加，那么Ａ和Ｄ也都参加。

--------------------------------------------------
我个人的做法,个人觉得这样做要简单一些,如果不懂的加我的QQ:12814441
#include <iostream>
using namespace std;
#include <string>
int main()
{
int a,b,c,d,e; //设置5个变量,分别表是不同的5个人
string f[2]={"不去","去"}; ///定义了一个字符串数组,f[1]={表示"不去"},f[2]={表示"去"}
for(a=0;a<=1;a++) /*a表示0,1;0表示不成立,就不去;1表示成立,就去*/
{for(b=0;b<=1;b++) /*b表示0,1;0表示不成立,就不去;1表示成立,就去*/
for(c=0;c<=1;c++) /*c表示0,1;0表示不成立,就不去;1表示成立,就去*/
{ if(b!=c) //a不能等c
for(d=0;d<=1;d++) /*d表示0,1;0表示不成立,就不去;1表示成立,就去*/
for(e=0;e<=1;e++) /*e表示0,1;0表示不成立,就不去;1表示成立,就去*/
{if(d!=e) //d不能等于e
if(e==1&&a&&b) /// 只有当e有成立时; a,b就必然成立

if((a&&b||!a)&&(b||c)&&(c&&d||!(c||d))&&(d||e)||(e&&a&&b)) /*根据条件进很逻辑判断*/
cout<<"A"<<f[a]<<" "<<"B"<<f[b]<<" "<<"C"<<f[c]<<" "<<"D"<<f[d]<<" "<<"E"<<f[e]<<" "<<endl;
} //if
} //if
} //for
return 0; //反回到主函数
}

#195

野比2007-07-21 00:38

最近忙到疯了。有时间抽空再来统计，不好意思了

#196

freshman422007-07-23 15:39

[CODE]第三题

#include <iostream>
using namespace std;
int main()
{
char outprint[10]={'T','J','1','2','3','4','5','6','7','8'};
char arryout[20][20];
int n;
cout<<"please input a integer(less than 20)";
cin>>n;
for(int i=0;i<=n/2;i++)
{
for(int j=i;j<n-i;j++)
{
arryout[i][j]=outprint[i];
arryout[j][i]=outprint[i];
arryout[n-i-1][j]=outprint[i];
arryout[j][n-i-1]=outprint[i];
}
}
for(int g=0;g<n;g++)
{
for(int h=0;h<n;h++)
cout<<arryout[g][h]<<" ";
cout<<endl;
}
return 0;
}[/CODE]

#197

a1211547452007-07-26 12:16

LZ~~~第九页126楼的14题有错吗？？？

#198

野比2007-07-26 19:21

以下是引用a121154745在2007-7-26 12:16:42的发言：
LZ~~~第九页126楼的14题有错吗？？？

没问题. 解答正确. 已测试..

#199

medicihophy2007-07-29 13:58

第二题感觉有点傻：
if A参加 AccordingTO Rule 1 then B参加；
Because B参加 AccordingTO Rule 2 then C不参加；
Because C不参加 if D参加，there is a error that Not satisfied Rule 3,so D不参加；
if E参加 AccordingTO Rule 5,then A参加 and D参加，but D不参加，so E不参加；
then AccordingTO Rule 4,Because D不参加 and E不参加，there is a error,so A不参加；

Because A不参加,AccordingTO Rule 5，then E不参加；
AccordingTO Rule 4,then D参加;AccordingTO Rule 3,then C参加；AccordingTO Rule 2 ，then B不参加；

the right answer is A不参加，B不参加,C参加，D参加，E不参加!

[此贴子已经被作者于2007-7-29 14:03:20编辑过]

#200

上杉达也2007-08-01 16:59

好像在那在那里看见过这些题目http://www.programfan.com/club/post-157289.html

答案http://www.programfan.com/club/post-190645.html

[此贴子已经被作者于2007-8-1 17:15:48编辑过]

#201

上杉达也2007-08-01 17:07

不会封我ID吧

[此贴子已经被作者于2007-8-1 17:17:31编辑过]