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

#102

laigaoat20052007-06-25 15:55

// 10.cpp author:laigaoat2005 data:2007.6.25
#include "iostream.h"
int main()
{
int input=0,count=0;
int i=0;
int ex=1;
while(ex)
{
cout<<"请输入每排正方形的个数：";
cin>>input;
for(i=input;i>0;i--)
{
count+=i*i;
}
cout<<"\n正方形个数是："<<count<<"\n";
input=0;
cout <<"请输入小正方形的边长：";
cin>>input;
count=input*input*count;
cout<<"大正方形的面积是："<<count<<"\n请选择你的操作：输入0退出，输入其它数值继续";
cin>>ex;
}
return 0;
}

#103

HJin2007-06-25 16:51

/*---------------------------------------------------------------------------
File name: C76-37.cpp
Author: HJin
Created on: 6/25/2007 01:12:43
Environment: Windows XP Professional SP2 English +
Visual Studio 2005 v8.0.50727.762

Modification history:

经典 76 道编程题之 37:

37. 已知 N 个正整数满足 K1+K2+...+Kn=M。求一组最佳的分解，使得
K1*K2*....*Kn 为最大。
例如：N=2时，给定 K1+K2=6,当 K1=3,K2=3 时，K1*K2=9 为最大

Analysis:

Do your math to establish the following recurrence formula

f(M, N) = M/N * f(M-M/N, N-1), if N>1
= M, if N=1.

My implementation is just a restating of this formula
in C++ language. You may want to develop an iterative soln.

Sample output:

M = 60, N = 17
max product 1719926784 = 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 4 * 4 * 4 * 4 * 4 * 4 *
4 * 4 * 4.
Press any key to continue . . .

Reference:

1. 野比, 相当经典的76道编程自虐题分享.无答案 at
https://bbs.bc-cn.net/viewthread.php?tid=147853

*/

#include <iostream>
#include <stdexcept>

using namespace std;

long f(int M, int N, int *k);

int main(int argc, char** argv)
{
int i;
int M=60;
int N=17;
int prod;
int* k = new int[N];

prod = f(M, N, k);

cout<<"M = "<<M<<", N = "<<N<<endl;

cout<<"max product "<<prod<<" = ";
for(i=0; i<N-1; ++i)
cout<<k[i]<< " * ";
cout<<k[N-1]<<"."<<endl;

delete [] k;

return 0;
}

long f(int M, int N, int* k)
{
static int index = 0;
if(M<N)
return 0;

if(N==1)
{
k[index] = M;
return M;
}
else
{
k[index] = M/N;
++index;
return M/N * f(M-M/N, N-1, k);
}
}

#104

HJin2007-06-25 19:21

/*---------------------------------------------------------------------------
File name: C76-67.cpp
Author: HJin
Created on: 6/25/2007 02:03:08
Environment: Windows XP Professional SP2 English +
Visual Studio 2005 v8.0.50727.762

Modification history:

经典 76 道编程题之 67 :

67. ( NOI'94.1_3 ) 一个实数数列共有Ｎ项，已知a(i)=(a(i-1)-a(i+1))/2+d，
（１〈i〈Ｎ）(N<60) , 键盘输入Ｎ，d，a(1)，a(n)，m，输出 a(m)。

Analysis:

A littl bit algebra shows that we are solving a tridiagonal linear
system (refer to you linear algebra textbook for solving Ax = b).

The tridiagonal linear system solver is standard and has been know
for almost 200 years.

Sample output:

i | a[i] | (a[i-1] - a[i+1]) / 2 + d
-----+----------------------+------------------------------
1 | 0 |
2 | 0.585786 | 0.585786
3 | 0.828427 | 0.828427
4 | 0.928932 | 0.928932
5 | 0.970563 | 0.970563
6 | 0.987807 | 0.987807
7 | 0.994949 | 0.994949
8 | 0.997908 | 0.997908
9 | 0.999133 | 0.999133
10 | 0.999642 | 0.999642
11 | 0.99985 | 0.99985
12 | 0.999942 | 0.999942
13 | 0.999965 | 0.999965
14 | 1.00001 | 1.00001
15 | 0.999939 | 0.999939
16 | 1.00013 | 1.00013
17 | 0.999672 | 0.999672
18 | 1.00079 | 1.00079
19 | 0.998091 | 0.998091
20 | 1.00461 | 1.00461
21 | 0.988873 | 0.988873
22 | 1.02686 | 1.02686
23 | 0.935147 | 0.935147
24 | 1.15657 | 1.15657
25 | 0.622007 | 0.622007
26 | 1.91255 | 1.91255
27 | -1.2031 | -1.2031
28 | 6.31876 | 6.31876
29 | -11.8406 | -11.8406
30 | 32 |
-----+----------------------+------------------------------
Press any key to continue . . .

Reference:

1. 野比, 相当经典的76道编程自虐题分享.无答案 at
https://bbs.bc-cn.net/viewthread.php?tid=147853

*/

#include <iostream>
#include <iomanip>

using namespace std;

/**
n --- number of equations
sub --- subdiagonal entries
diag --- diagonal entries
sup --- supdiagonal entries
b --- original rhs vector
x --- solution vector
*/
void triDiagonal(int n,
double* sub,
double* diag,
double* sup,
double* b,
double* x);

int main(int argc, char** argv)
{
int i;
int N=30;
double *a = new double[N];
double d = 1;
int m=5;

a[0] = 0;
a[N-1] = 32;

double* sub = new double[N-2];
double* sup = new double[N-2];
double* diag = new double[N-2];
double* x = &a[1];
double* b = new double[N-2];

for(i=0; i<N-2; ++i)
{
sub[i] = 1.0;
diag[i] = -2.0;
sup[i] = -1.0;
b[i] = -2.0*d;
}
b[0] += -a[0];
b[N-3] += a[N-1];

triDiagonal(N-2, sub, diag, sup, b, x);

//cout<<x[m]<<endl;

cout<<std::left<<setw(4)<<"i"<<" | "<<std::right<<setw(20)<<"a[i]"<<" | "<<std::left<<"(a[i-1] - a[i+1]) / 2 + d"<<endl;
cout<<"-----+----------------------+------------------------------\n";
i=0;
cout<<std::left<<setw(4)<<i+1<<" | "<<std::right<<setw(20)<<a[0]<<" | "<<std::left<<" "<<endl;
for(i=1; i<N-1; ++i)
{
cout<<std::left<<setw(4)<<i+1<<" | "<<std::right<<setw(20)<<a[i]<<" | "<<std::left<<setw(20)<<( a[i-1] - a[i+1] )/2.0 + d<<endl;
}
cout<<std::left<<setw(4)<<i+1<<" | "<<std::right<<setw(20)<<a[N-1]<<" | "<<std::left<<" "<<endl;
cout<<"-----+----------------------+------------------------------\n";

delete [] a;
delete [] sub;
delete [] diag;
delete [] sup;
delete [] b;

return 0;
}

void triDiagonal(int n,
double* sub,
double* diag,
double* sup,
double* b,
double* x)
{
int i;
double factor;

// forward elimination
for (i = 1; i < n; ++i)
{
factor = -sub[i-1] / diag[i-1];
diag[i] += factor * sup[i-1];
b[i] += factor * b[i-1];
}

// backward substitution
x[n-1] = b[n-1]/ diag[n-1];
for(i = n-2; i >=0; --i)
x[i] = (b[i] - sup[i]*x[i+1]) / diag[i];
}

#105

HJin2007-06-25 19:56

/*---------------------------------------------------------------------------
File name: C76-74.cpp
Author: HJin
Created on: 6/25/2007 04:45:37
Environment: Windows XP Professional SP2 English +
Visual Studio 2005 v8.0.50727.762

Modification history:

经典 76 道编程题之 74 :

74. (NOI'95.1_5) m、n为整数，且满足下列两个条件：
　　① m、n∈｛1, 2, …, k｝, (1≤k≤109)
② (n^2－m*n－m^2)^2＝1
编一程序, 由键盘输入k, 求一组满足上述两个条件的 m、n, 并且使m^2＋n^2
的值最大.
例如, 若 k＝1995, 则 m＝987, n＝1597 时, 则 m、n 满足条件, 且可使
m^2＋n^2的值最大.

Analysis:

Loop over m and n, O(k^2) algorithm.

Sample output:

3524578
m = 987, n = 1597, m^2 + n^2 = 3524578
Press any key to continue . . .

Reference:

1. 野比, 相当经典的76道编程自虐题分享.无答案 at
https://bbs.bc-cn.net/viewthread.php?tid=147853

*/

#include <iostream>
#include <iomanip>

using namespace std;

int main(int argc, char** argv)
{
int m;
int n;
int temp;
int tempSquare;
int max=2;
int k=1995;
int mKeeper=1;
int nKeeper=1;

/**
O(k^2) algorithm --- just a 2-loop.
*/
for(m=1; m<=k; ++m)
{
for(n=1; n<=k; ++n)
{
temp = n*(n-m)-m*m;
if(temp*temp == 1)
{
tempSquare=m*m+n*n;
if(max < tempSquare)
{
max = tempSquare;
mKeeper = m;
nKeeper = n;
}
}
}
}

cout<<max<<endl;
cout<<"m = "<<mKeeper<<", n = "<<nKeeper<<", m^2 + n^2 = "<<mKeeper*mKeeper + nKeeper*nKeeper<<endl;

return 0;
}

#106

HJin2007-06-26 03:14

To 野比：

HCL's #6 tested to be correct (at least for n = 5, 4).

To HCL:

If you could write some comments about your idea inside the source code, that would be better for a viewer to follow the algorithm (instead of just copying your souce code).

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
Enter a number : 5
25 24 23 22 21
20 19 18 17 16
15 14 13 12 11
10 9 8 7 6
5 4 3 2 1

1 3 4 10 11
2 5 9 12 19
6 8 13 18 20
7 14 17 21 24
15 16 22 23 25

1 16 15 14 13
2 17 24 23 12
3 18 25 22 11
4 19 20 21 10
5 6 7 8 9

Press any key to continue . . .

Enter a number : 4
16 15 14 13
12 11 10 9
8 7 6 5
4 3 2 1

1 3 4 10
2 5 9 11
6 8 12 15
7 13 14 16

1 12 11 10
2 13 16 9
3 14 15 8
4 5 6 7

Press any key to continue . . .

[此贴子已经被作者于2007-6-26 3:20:39编辑过]

#107

wfpb2007-06-26 11:16

我看第4题这个简单的没人挑啊。。。

int fun(int n)
{
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<i+n;j++)
            cout<<(j-1)%n+1<<\" \";
        cout<<endl;
    }
}
void main()
{
    fun(5);
}

#108

smartwind2007-06-26 11:36

第三题，C++：

程序代码：

#include<iostream>
using namespace std;

void print(int,int,int);

int n;

int main()
{
cin>>n;
if(n>=20||n<=3)
  return 0;
int i,j;
for(i=1;i<=n;i++)
{
  for(j=1;j<=n;j++)
  {
   if(i==1||i==n||j==1||j==n)
    cout<<\"T\";
   else if(i==2||i==n-1||j==2||j==n-1)
    cout<<\"J\";
   else
    print(1,i,j);
  }
  cout<<endl;
}
system(\"pause\");
}

void print(int a,int i,int j)
{
if(a>n)
  return;
if(i-2==a||i==n-a-1||j-2==a||j==n-a-1)
  cout<<a;
else
  print(a+1,i,j);
return;
}

#109

smartwind2007-06-26 11:50

第九题：

#include<iostream>
using namespace std;

#define N 16

#define f(n1,n2,n3,n4) {n1/=2;n2/=2;n3/=2;n4+=n1+n2+n3;}

int main()
{
int a,b,c,d;
a=b=c=d=N;
f(a,b,c,d);
f(b,c,d,a);
f(c,d,a,b);
f(d,a,b,c);
cout<<a<<endl<<b<<endl<<c<<endl<<d<<endl;
system(\"pause\");
return 0;
}

#110

wfpb2007-06-26 12:47

第8题：
不知道是不是下面的意思?

#include <cmath>
template<class T>
class BYTE
{
    char *ptr;
    unsigned num;
public:
    BYTE()
    {
        num=sizeof(T)*8;
        ptr=new char[num];
        if(!ptr)return;
        memset(ptr,0,num);
    }
    BYTE(T t)
    {
        num=sizeof(T)*8;
        ptr=new char[num];
        if(!ptr)return;
        memset(ptr,0,num);
        for(int i=0;i<num;i++)
            ptr[i]=(t&(T)pow(2,i))==0?0:1;
    }
    BYTE(const BYTE<T>& byte)
    {
        num=byte.num;
        ptr=new char[num];
        if(!ptr)return;
        memset(ptr,0,num);
        for(int i=0;i<num;i++)
            ptr[i]=byte.ptr[i];
    }
    ~BYTE()
    {
        num=0;
        delete[]ptr;
    }
    BYTE<T>& operator=(BYTE<T>& byte)
    {
        memset(ptr,0,num);
        for(int i=0;i<num;i++)
            ptr[i]=byte.ptr[i];
        return *this;
    }
    BYTE<T>& operator=(T t)
    {
        *this=BYTE<T> byte(t);
        return *this;
    }
    BYTE operator+(BYTE<T> bt)
    {
        BYTE<T> temp;
        char t=0;
        for(int i=0;i<num;i++)
        {
            temp.ptr[i]=(t+ptr[i]+bt.ptr[i])%2;
            t=(t+ptr[i]+bt.ptr[i])/2;
        }
        return temp;
    }
    BYTE operator|(BYTE<T> bt)
    {
        BYTE<T> temp;
        char t=0;
        for(int i=0;i<num;i++)
        {
            temp.ptr[i]=(t+ptr[i]+bt.ptr[i])%2;
            t=(t+ptr[i]+bt.ptr[i])/2;
        }
        return temp;
    }
    operator T()
    {
        return GetValue();
    }
    T GetValue()
    {
        T data;
        memset(&data,0,sizeof(T));
        for(int i=0;i<num;i++)
        {
            data|=T(int(ptr[i])*pow(2,i));
        }
        return data;
    }
    friend ostream& operator<<(ostream &os,BYTE<T>& byte)
    {
        for(int i=byte.num-1;i>=0;i--)
            os<<char(byte.ptr[i]+48);
        os<<endl;
        return os;
    }
};

测试用例

void main()
{
//    fun(5);
    BYTE<int> a=3;
    BYTE<int> b=3;
    cout<<b<<endl;
    cout<<a<<endl;
    cout<<b+a<<endl;
    cout<<(b|a)<<endl;
    cout<<b.GetValue()<<endl;
    int c=b;
    cout<<c<<endl;
//    string s1=\"1\";
}

#111

zkkpkk2007-06-26 13:36

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

程序代码：

/*
3. 打印一个 N*N 的方阵，Ｎ为每边
字符的个数（３＜Ｎ＜２０）, 要求最
外一层为\"T\", 第二层为\"J\", 从第三层
起每层依次打印数字 1,2,3,...
*/
#include <iostream.h>
#define MAX 22

int main()
{
    int i=0,j=0,m=1,n=3;
    char charr[MAX][MAX];
    char ch1='T';
    char ch2='J';
    //char tmp[2];

    for(i=0;i<MAX-1;i++)
        for(j=0;j<MAX-1;j++)
            charr[i][j]='a';

    cout<<\"输入N的值：\";
    cin>>n;
    int a=0,b=n-1,c=n-1,d=0;
    bool bo=false;

    while(m<=(n-4)/2+1)
    {
        for(i=0;i<n;i++)
        {
            if(a==0)
            {
                if(charr[a][i]=='a')
                    charr[a][i]=ch1;
                continue;
            }
            if(a==1)
            {
                if(charr[a][i]=='a')
                    charr[a][i]=ch2;
                continue;
            }
            if(charr[a][i]=='a')
                charr[a][i]=(char)m+(char)48;
        }

        for(i=0;i<n;i++)
        {
            if(b==n-1)
            {
                if(charr[i][b]=='a')
                    charr[i][b]=ch1;
                continue;
            }
            if(b==n-2)
            {
                if(charr[i][b]=='a')
                    charr[i][b]=ch2;
                continue;
            }
            if(charr[i][b]=='a')
                charr[i][b]=(char)m+(char)48;
        }

        for(i=n-1;i>=0;i--)
        {
            if(c==n-1)
            {
                if(charr[c][i]=='a')
                    charr[c][i]=ch1;
                continue;
            }
            if(c==n-2)
            {
                if(charr[c][i]=='a')
                    charr[c][i]=ch2;
                continue;
            }
            if(charr[c][i]=='a')
                charr[c][i]=(char)m+(char)48;
        }

        for(i=n-1;i>=0;i--)
        {
            if(d==0)
            {
                if(charr[i][d]=='a')
                    charr[i][d]=ch1;
                continue;
            }
            if(d==1)
            {
                if(charr[i][d]=='a')
                    charr[i][d]=ch2;
                continue;
            }
            if(charr[i][d]=='a')
                charr[i][d]=(char)m+(char)48;
            bo=true;
        }

        a++;d++;c--;b--;
        if(bo==true)
            m++;
    }

    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
            cout<<charr[i][j]<<' ';
        cout<<endl;
    }
    return 0;
}

[此贴子已经被作者于2007-6-27 21:38:23编辑过]

#112

wfpb2007-06-26 16:06

第12题：不知道是不是这个意思.
打印出来的0,1,2,3分别表示:
0——向左
1——向右
2——向下
3——向上
不知道如何更高效率

程序代码：

class Coordinate
{
//注意：坐标代表的数字与2维数组相反。
    int abscissa;    //横坐标
    int ordinate;    //纵坐标
    int nWidth,nHeight;
    int dir;
public:
    Coordinate(int a=-1,int b=-1,int w=0,int h=0)
    {
        dir=-1;
        abscissa=a;
        ordinate=b;
        nWidth=w;
        nHeight=h;
    }
    bool ToLeft()
    {
        if(abscissa==0)
            return false;
        abscissa--;
        dir=0;
        return true;
    }
    bool ToRight()
    {
        if(abscissa==nWidth)
            return false;
        abscissa++;
        dir=1;
        return true;
    }
    bool ToDown()
    {
        if(ordinate==nHeight)
            return false;
        ordinate++;
        dir=2;
        return true;
    }
    bool ToUp()
    {
        if(ordinate==0)
            return false;
        ordinate--;
        dir=3;
        return true;
    }
    bool DirOperate(int i)
    {
        if(abs(dir-i)==1 && (dir+i)*2!=6)
            return false;
        switch(i)
        {
        case 0:return ToLeft();
        case 1:return ToRight();
        case 2:return ToDown();
        case 3:return ToUp();
        default:return false;
        }
    }
    bool operator==(Coordinate cd)
    {
        return abscissa==cd.abscissa&&ordinate==cd.ordinate;
    }
    void SetRange(int w,int h)
    {
        nWidth=w;
        nHeight=h;
    }
    int GetAbscissa()
    {
        return abscissa;
    }
    int GetOrdinate()
    {
        return ordinate;
    }
};
#include <deque>
class Maze
{
    Coordinate inner;    //入口
    Coordinate outer;    //出口
    int ** ppMap;
    int nWidth,nHeight;
private:
    bool MazeLine(Coordinate in,deque<int>&s)
    {
        Coordinate temp=in;
        for(int i=0;i<4;i++)
        {
            in=temp;
            if(in.DirOperate(i))
            {
                if(ppMap[in.GetOrdinate()][in.GetAbscissa()]==1)
                {
                    if(in==outer||MazeLine(in,s))
                    {
                        s.push_front(i);
                        return true;
                    }
                }
            }
        }
        return false;
    }
public:
    Maze(Coordinate in,Coordinate out,int **map,int width,int height)
    {
        in.SetRange(width,height);
        ppMap=new int*[height];
        for(int i=0;i<height;i++)
            ppMap[i]=new int[width];
        for (int m=0;m<height;m++)
            for (int n=0;n<width;n++)
                ppMap[m][n]=map[m][n];
        inner=in;
        outer=out;
    }
    bool MazeLine(deque<int>&dq)
    {
        return MazeLine(inner,dq);
    }
};

int arr[][10]=
{
    {0,1,0,0,0,0,0,0,0,0},
    {0,1,0,1,1,1,1,0,1,0},
    {0,1,1,1,0,0,1,0,1,0},
    {0,1,0,0,0,0,1,1,1,0},
    {0,1,0,0,0,0,0,0,0,0},
    {0,1,1,1,1,1,1,1,1,0},
    {0,1,0,0,0,1,0,1,0,0},
    {0,1,0,0,0,1,0,1,0,0},
    {0,1,0,1,1,1,0,1,1,0},
    {0,1,0,0,0,0,0,0,1,0}
};

void main()
{
    int **maze=new int*[10];
    for(int m=0;m<10;m++)
        maze[m]=new int[10];

    for(int i=0;i<10;i++)
        for(int j=0;j<10;j++)
            maze[i][j]=arr[i][j];
    Maze mz(Coordinate(1,0),Coordinate(8,9),maze,10,10);
    deque<int>dq;
    if(mz.MazeLine(dq))
        cout<<\"\nsuccess\"<<endl;
    else
        cout<<\"\nfail\"<<endl;
    copy(dq.begin(),dq.end(),ostream_iterator<int>(cout));
}

#113

smartwind2007-06-27 10:47

75题：

程序代码：

#include <iostream>
using namespace std;

#define N 3

const int a[N]={31,15,7};
//{20,19,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1};
//{200,179,157,140,139,110,103,101,97,90,80,64,51,45,36,25,14,10,9,6};
int b[N];

bool fun(int n,int i)
{
if(n==0)
  return true;
if(i>=N)
  return false;
if(n<a[i])
  return fun(n,i+1);
if(fun(n-a[i],i))
{
  b[i]++;
  return true;
}
else
  return fun(n,i+1);
}

int main()
{
int n,i,k;
do
{
  k=0;
  cin>>n;
  if(n>10000||n<0)  //限制0<n<10000
   goto CON;
  if(fun(n,0))   //有解则输出结果
  {
   for(i=0;i<N;i++)
    k+=b[i];
   cout<<k<<endl;
   for(i=0;i<N;i++)
   {
    if(b[i]>0)
    {
     cout<<a[i]<<\"*\"<<b[i]<<\" \";
     b[i]=0;
    }
   }
   cout<<endl;
  }
  else
CON:  cout<<\"no answer\"<<endl;
}
while(n!=0);   //输入0结束
return 0;
}

#114

weishj2007-06-27 11:16

第37题,不知题意理解的对不对

/*file name:37.cpp
37. 已知 N 个正整数满足 K1+K2+...+Kn=M。求一组最佳的分解，使得
K1*K2*....*Kn 为最大。
例如：N=2时，给定 K1+K2=6,当 K1=3,K2=3 时，K1*K2=9 为最大*/
#include <iostream>
#include <iomanip>
using namespace std;
int main()
{
int N=0,M=0,sum=0,diff=0,product=1;
int* arr=NULL;
float ave=0.0;
cout<<"输入数字个数N:"<<endl;
cin>>N;
cout<<"输入这些数字的和M:"<<endl;
cin>>M;
arr=new int[N];
ave=float(M)/float(N);
sum=int(ave)*N;
diff=M-sum;//diff肯定小于N
for(int i=0;i<N;i++)
{
if(i<diff) arr[i]=1+int(ave);
else arr[i]=int(ave);
}
cout<<"一个最佳分解是:"<<endl;
for(int j=0;j<N;j++)
{
cout<<setw(5)<<arr[j];
product*=arr[j];
}
cout<<endl<<"最大乘积是:"<<product<<endl;
delete []arr;
return 0;
}

#115

zkkpkk2007-06-27 16:24

41题链表合并

程序代码：

/*
41. (合并链表) 已知两个链
表 AN={a1,a2,...an},
BN={b1,b2,...bm},
将其合并为一个链表
CN={a1,b1,a2,b2,...}
*/

#include <iostream.h>

/*节点结构体Node*/
struct Node
{
int data;
Node* next;
};
/*结构体头指针*/
Node* head1 = new Node;
Node* head2 = new Node;
Node* head3 = new Node;

/*添加一个新节点*/
void Push(Node* head,int data)
{
    Node* node = new Node;
    node->data = data;
    node->next = head->next;
    head->next = node;
}
/*输出链表*/
void Display(Node* head)
{
    Node* temp=head->next;
    while(temp!=NULL)
    {
        cout<<temp->data<<'\t';
        temp=temp->next;
    }
    cout<<endl;
}
/*初始化一条链表*/
Node* Info(Node* head,int a)
{
    for(int i=0;i<a;i++)
        Push(head,i);
    return head;
}
Node* Info_Input(Node* head,int a)
{
    cout<<\"请输入数据：\"<<endl;
    for(int i=0;i<a;i++)
    {
        int value;
        cout<<\"第\"<<i+1<<\"个元素\"<<endl;
        cin>>value;
        Push(head,value);
    }
    return head;
}
/*链表归并算法*/
Node* UniteLink(Node* head1,Node* head2,Node* head3)
{
    Node *p1=NULL,*p2=NULL;
    Node* temp1=head1->next;
    Node* temp2=head2->next;
    Node* temp3=head3;
    temp3->next=temp1;
    while((temp1!=NULL) && (temp2!=NULL))
    {
        p1=temp1;
        temp1=temp1->next;
        p1->next=temp2;
        p2=temp2;
        temp2=temp2->next;
        p2->next=temp1;
        if((temp1==NULL) && (temp2!=NULL))
        {
            p2->next=temp2;
            break;
        }
        else if((temp1!=NULL) && (temp2==NULL))
        {
            p2->next=temp1;
            break;
        }
    }
    return temp3;
}

int main()
{
    head1->next=NULL;
    head2->next=NULL;
    head3->next=NULL;
    int a;
    cout<<\"请输入链表A的数据长度：\";
    cin>>a;
    Info_Input(head1,a);
    cout<<\"构造链表A：\"<<'\t';
    Display(head1);
    cout<<\"请输入链表B的数据长度：\";
    cin>>a;
    Info_Input(head2,a);
    cout<<\"构造链表B：\"<<'\t';
    Display(head2);
    UniteLink(head1,head2,head3);
    cout<<\"合并后的链表CN：\"<<'\t';
    Display(head3);
    return 0;
}

#116

HJin2007-06-27 17:50

To 野比：

If you have time, you may want to do some work to

1) give people credits
2) let people know which problem is solved.

Thanks,

HJin

#117

kai2007-06-27 20:03

wfpb,

你在107楼关于第四题的代码是不正确的，看来你没有完全理解题意。
题目的本意是要你给出所有的解，而不是其中的某一种。

这道题是很难的，并不是什么太简单了，大家都不做了。

#118

zkkpkk2007-06-27 21:39

程序代码：

/*回旋填数*/
#include <stdio.h>
#include <iostream.h>

int array[11][11];
int temp;
int ROW;

void godown(int &m,int &a)
{
    for(temp=1;temp<=ROW;temp++)
        if(array[temp][a]==0)
            array[temp][a]=m++;
    a++;
}
void goright(int &m,int &b)
{
    for(temp=1;temp<=ROW;temp++)
        if(array[b ][temp]==0)
            array[b ][temp]=m++;
    b--;
}
void goup(int &m,int &c)
{
    for(temp=ROW;temp>0;temp--)
        if(array[temp][c]==0)
            array[temp][c]=m++;
    c--;
}
void goleft(int &m,int &d)
{
    for(temp=ROW;temp>0;temp--)
        if(array[d][temp]==0)
            array[d][temp]=m++;
    d++;
}

int main()
{
    int a,b,c,d,max,m;
    cout<<\"请输入缧旋方阵的维数n(不能大于10):\";
    cin>>ROW;
    cout<<endl;
    for(a=1;a<=ROW;a++)
        for(b=1;b<=ROW;b++)
            array[a][b ]=0;
    m=1;
    a=d=1;
    b=c=ROW;
    max=ROW*ROW;

    while(m<=max)
    {
        godown(m,a);
        goright(m,b);
        goup(m,c);
        goleft(m,d);
    }
    for(a=1;a<=ROW;a++)
    {
        for(b=1;b<=ROW;b++)
            printf(\"%3d \",array[a][b ]);
        cout<<endl;
    }
    return 0;
}

程序代码：

/*倒填*/
#include <iostream.h>
#define MAX 5

int main()
{
    int i=0, j=0;
    int array[MAX][MAX];
    int t=MAX*MAX;

    for(i=0;i<MAX;i++)
        for(j=0;j<MAX;j++)
            array[i][j]=t--;

    for(i=0;i<MAX;i++)
    {
        for(j=0;j<MAX;j++)
            cout<<array[i][j]<<'\t';
        cout<<endl;
    }

return 0;
}

[此贴子已经被作者于2007-6-29 11:43:55编辑过]

#119

野比2007-06-27 22:08

To HJin,

I'm very sorry to tell you that I do not have much time recently...
My boss got me plenty of works to do...

You can edit my posts by yourself, since you are now the moderator of the cpp classroom...
I don't have as much time as you do...

Thanks,
Nobi

#120

aipb20072007-06-27 22:47

你也是斑竹，他也是斑竹，所以不得行。

还是你自己能来，等有空了再搞吧，呵呵~工作要紧！

#121

野比2007-06-27 22:56

终于统计完了...

只有不到7个小时睡觉了... 澡还没洗...

工资果然不是白拿的...

#122

killer_l2007-06-28 08:41

学习中..........

#123

yuyunliuhen2007-06-28 11:38

回家慢慢研究！

#124

weishj2007-06-28 19:46

/* 65. ( NOI'94.1_1 ) 键盘输入一个仅由小写字母组成的字符串，输出以该串中任
取Ｍ个字母的所有排列及排列总数。*/
#include <iostream>
#define MAXN 100 //输入的字符串的最大长度,可任意改
#define MAX 500 //本程序所支持的最大排列数,可改
using namespace std;
int a[MAXN];
char result[MAX][MAXN];
int x=0,footer=0; //x记录组合数,x和footer作为result的行标和列标
void combin(int m,int n,char *tt); //求得从tt所指字符中选出n个字符的所有组合
int f(int n);
void permute(char*,int,int); //输出已知字符串的全排列
int main()
{
char *tt;
char n[5],data[MAXN];
int m;
cout<<"请输入字符串:"<<endl;
cin>>data;
do
{
cout<<"要取几个字符?(该数字必须小于或者等于"<<strlen(data)<<")"<<endl;
cin>>n;
cin.sync();
cin.clear();
m=strlen(data);
}while(m<atoi(n));
tt=data;
a[0]=atoi(n);
combin(m,atoi(n),tt);
int sum=x*f(a[0]);
cout<<"一共有"<<sum<<"种排列:"<<endl;
for(int i=0;i<x;i++)
permute(result[i],0,atoi(n));
return 0;
}
void combin(int m,int n,char *tt)
{
int i,j;
for (i=m;i>=n;i--)
{
a[n]=i;
if (n>1)
combin(i-1,n-1,tt);
else
{
x++;
for(j=a[0];j>0;j--)
result[x-1][footer++]=*(tt+a[j]-1);
footer=0;
}
}
}
int f(int n)
{
int s=1;
for(int i=1;i<=n;i++)
s*=i;
return s;
}
void permute(char a[],int m,int n)
{
int i;
if(m<n-1)
{
permute(a,m+1,n);
for (i=m+1;i<n;i++)
{
swap(a[m],a[i]);
permute(a,m+1,n);
swap(a[m],a[i]);
}
}
else
cout<<a<<endl;
}

[此贴子已经被作者于2007-6-28 19:47:53编辑过]

#125

huozoo2007-06-28 20:36

回环```
#include<iostream>
#include<iomanip>
using namespace std;
int main()
{
const int n=6;
int a[n][n]={0},i;
a[0][0]=1;
for(int x=0;x<n/2+1;x++)
{
for(i=x;i<n-x;i++)
if(a[x][i]==0)
a[x][i]=a[x][i-1]+1;
for(i=x;i<n-x;i++)
if(a[i][n-x-1]==0)
a[i][n-x-1]=a[i-1][n-x-1]+1;
for(i=n-x-1;i>=x;i--)
if(a[n-x-1][i]==0)
a[n-x-1][i]=a[n-x-1][i+1]+1;
for(i=n-x-1;i>=x+1;i--)
if(a[i][x]==0)
a[i][x]=a[i+1][x]+1;
}
for(int q=0;q<n;q++)
{
cout<<endl;
for(int w=0;w<n;w++)
cout<<setw(5)<<a[q][w];
cout<<endl;
}
cout<<endl;
return 0;
}
自己写着玩的,没想到这还有题目```发上来共享

#126

huozoo2007-06-28 21:07

14
#include<iostream>
using namespace std;
int main()
{
const int n=100;
int i,j;
char t,a[n];
for(i=0;i<n/2;i++)
a[i]='*';
for(i=n/2;i<n;i++)
a[i]='0';
for(i=0;i<n;i++)
cout<<a[i]<<" ";
cout<<endl;cout<<endl;cout<<endl;
for(i=n/2;i<n;i++)
for(j=i;j>0&&a[j-1]!='0';j--)
{t=a[j];a[j]=a[j+1];a[j+1]=t;}
for(i=0;i<n;i++)
cout<<a[i]<<" ";
cout<<endl;
return 0;
}没运行过,没编译器,哪位兄弟拿去编下哈```我只能在网吧上网```

[此贴子已经被作者于2007-7-1 22:08:16编辑过]

#127

huozoo2007-06-28 21:10

没去看哪题谁做过,不好意思```

#128

huozoo2007-06-28 21:13

老大有没答案.什么时候发布和我说下,看到有几道题让我兴奋了啊```可是能力不行```没编译器让我调试```谢谢版主老大

#129

jojo070212007-06-29 11:16

找到了个学习的好地方！学习学习！

#130

zkkpkk2007-06-29 11:49

补充118楼第6题（2），对HCL兄蛇型填数的改进，也不知道算不算改进？因为用三目符来代替if了

#include <iostream.h>
#define MAX 5

int main()
{
    int sum=0, j=0, t=1, start=0, end=0;
    static int array[MAX][MAX];
    for(sum = 0; sum < 2*MAX-1; sum++)
    {
        start = (sum < MAX)?0:sum-(MAX-1);        //越过对角线后start和end范围递减
        end = (sum < MAX)?sum:(MAX-1);
        for(j = start; j <= end; j++)
            //(sum%2)控制环绕方向==0和!=0的时候分别向不同的对角方向环绕
            //随着j的增加sum-j渐小array[j][sum-j]时行渐大列渐小，
            //array[sum-j][j]时相反
            (sum%2!=0)?(array[j][sum-j] = t++):(array[sum-j][j] = t++);
    }
    for(sum = 0; sum < MAX; sum++)
    {
        for(j = 0; j < MAX; j++)
            cout<<array[sum][j]<<'\t';
        cout<<endl<<endl;
    }

return 0;
}

[此贴子已经被作者于2007-7-3 20:18:37编辑过]

#131

huozoo2007-06-29 12:47

有没什么好网站能下各种编译器的，要能下的哦```谢```

#132

zkkpkk2007-06-29 13:35

蚂蚁那里有个devC++

#133

aipb20072007-06-29 13:56

去搜索下主流编译器，网络里都有下载的！

#134

lous1222007-06-29 16:51

回复：（kai）关于第三题, 如果仔细观察一下这个图,那...

该程序有错误！

#135

zkkpkk2007-06-29 20:06

楼主写错了，我在118的是第6题，130楼补充了蛇型

#136

野比2007-06-29 20:37

不好意思... 太忙了, 没有仔细检查... 改正

#137

zkkpkk2007-07-02 22:50

这个题居然没有人做

//*************************************************************************
//7. 读入一行文本，包含若干个单词（以空格间隔，％结尾）。将其中以 A 开头的
//单词与以 N 结尾的单词，用头尾交换的办法予以置换。
//*************************************************************************
[code]
#include <iostream.h>

int main()
{
    char str[]=\"I am a sb who are you%\";
    char *p,*q,t;
    p=str;

    while(*p!='%')
    {
        if(*p==' ')
            cout<<*p++;        //输出空格
        q=p;
        while(*p!=' ' && *p!='%')
            p++;
        if(*p==' ')
            if(*q=='a' || *(p-1)=='n')
            {
                t=*q;
                *q=*(p-1);
                *(p-1)=t;
            }
        while(q!=p)
            cout<<*q++;        //输出处理后的子串
    }
return 0;
}

[此贴子已经被作者于2007-7-2 22:53:54编辑过]

#138

HJin2007-07-03 04:47

/*---------------------------------------------------------------------------
File name: C76-76.cpp
Author: HJin
Created on: 7/1/2007 02:30:50
Environment: Windows XP Professional SP2 English +
Visual Studio 2005 v8.0.50727.762

Modification history:

7/2/2007 15:39:35
-----------------------------------------------------------
1. totally ignore the hints in the original problem statement;
2. directly outputs the result for L = 3..6;
3. wrap the recursive call do_find() in find();
4. optimize the code so that it is more readable.

7/2/2007 07:15:41
-----------------------------------------------------------
add some analysis and correct a bug for S = 2.

经典 76 道编程题之 76:

76. (省刻度尺问题)给定长度为 L 的直尺, L 为整数, 且 L≤ 40. 为了能一次直接
量出 1, 2, ..., L 的各种长度, 该尺内部至少要有多少条刻度 ? 请输出最少刻度
数(不含两端点)及每个刻度的位置. 测量长度时可利用两端点, 其位置分别为 0, L.

输入
由键盘输入 L.
输出
用文本文件按以下格式输出结果(文件名: ANS2.TXT):
第 1 行: S(最少刻度数)
第 2 行: 尺内 S 个刻度的位置
第 3 行至第 L+2 行: 每行输出 3 个用空格隔开的整数 t m n, 其中
1≤t≤L 为要测量的各长度, m, n 依次为该长度的起止刻度 (m<n).

例: 如果 L=6, 则一个正确的输出是:
2
1 4 提示:
1 0 1 (1) 最少刻度数 S 应满足:
2 4 6 C[S+2,2]=(S+2)*(S+1)/2≥L.
3 1 4 (2) 除两端点外, 第一个刻度可取为
4 0 4 A[1]=1, 第二个刻度可在 1, L-2,
5 1 6 L-1 这三个数中选取.
6 0 6

(Note that if we handle the case S<=2 (for L =2, 3, 4, 5, 6) directly,
we can totally ignore the hints.)

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

Let
a_0 < a_1 < ... < a_S < a_{S+1} (1)
be the markings on the ruler, where a_0 = 0, a_{S+1} = L.
We are searching a_1 to a_S.

A little bit high shcool math shows that
L/2 >= S >= (-3 + \sqrt{ 8L + 1 } )/2.
This tell us we should start our search at (-3 + \sqrt{ 8L + 1 } )/2.
It is easy to see that (1) gives a soln if and only if the set
{a_j - a_i: S+1>= j > i >=0}
equals the set {1, 2, ..., L}.

Sample output:
-----------------------------------------------------------

Please input the value for L (2 <= L <= 40)): 6
1 4
1 0 1
2 4 6
3 1 4
4 0 4
5 1 6
6 0 6
Press any key to continue . . .

Please input the value for L (2 <= L <= 40)): 40
9
1 2 3 4 10 17 24 29 35
1 0 1
2 0 2
3 0 3
4 0 4
5 24 29
6 4 10
7 3 10
8 2 10
9 1 10
10 0 10
11 24 35
12 17 29
13 4 17
14 3 17
15 2 17
16 1 17
17 0 17
18 17 35
19 10 29
20 4 24
21 3 24
22 2 24
23 1 24
24 0 24
25 4 29
26 3 29
27 2 29
28 1 29
29 0 29
30 10 40
31 4 35
32 3 35
33 2 35
34 1 35
35 0 35
36 4 40
37 3 40
38 2 40
39 1 40
40 0 40
Press any key to continue . . .

Reference:

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

*/

#include <iostream>
#include <fstream>
#include <string>

using namespace std;

#define N 40

/**
global buffers and variables.
*/

int a[N+1]; // only a_0 to a_{S+1} are used.

// flags for 0..L --- if one number is used, it is set to 1
// only b_0 to b_L are used. Same thing for c[] and d[].
int b[N+1];

/** A soln will give us the following relation:
i = d[i] - c[i], i = 1..L.
*/
int c[N+1];
int d[N+1];

// mininum number of markings on the ruler
int S;

// total length of the ruler
int L;

/**
Recursive search function.
@param i --- the index in 2..S such that a_i is not assigned a vaule yet
@param p --- lower bound for a[i] (note it is not lower bound for i)
@param r --- upper bound for a[i]

Time complexity is O(L*S^2).
*/
void do_find(int i, int p, int r);

/**
A wrapper for do_find().

Time complexity is O(L^2*S^2).
*/
void find(int L);

/**
Check if we have a soln.

Time complexity is O(S^2).
*/
bool isSoln();

/**
Print the soln to an output stream.
*/
void print(std::ostream& os = cout);

void print(const string& s, std::ostream& os = cout);

int main(int argc, char** argv)
{
cout<<"Please input the value for L (2 <= L <= 40)): ";
cin>>L;

if(L<2 || L >40)
{
cout<<"incorrect input value.\n";
exit(1);
}

find(L);

return 0;
}

void do_find(int i, int p, int r)
{
// a[i] can be one of p..r
for (int j = p; j <= r; ++j) // O(L)
{
a[i] = j;

/** if all a_1 --- a_S are filled in
and they form a soln.

Clearly, this will be executed at most
once for the whole program.
*/
if ( i==S && isSoln() )
{

print();

std::ofstream ofs("ANS2.TXT");
if(!ofs)
{
cout<<"cannot open file ANS2.TXT.\n";
exit(1);
}

print(ofs);
ofs.close();

exit(1);
}

/**
This recursive call is very expensive. Most execution time
is wasted here.

Can you rewrite do_find() as an iterative procedure?
*/
if ( i<S && j< r )
{
//cout<<"i+1 = "<<i+1<<", j+1 = "<<j+1<<endl;
do_find(i+1, j+1, r); // recursive call
}
}
}

void print(std::ostream& os)
{
int i;

os<<S<<endl;

for(i=1; i<=S; ++i)
{
os<<a[i]<<" ";
}
os<<endl;

for(i=1; i<=L; ++i)
{
os<<i<<" "<<c[i]<<" "<<d[i]<<endl;
}
}

void print(const string& s, std::ostream& os)
{
os<<s;
}

void find(int L)
{
if(L<7)
{
string str;
ofstream ofs("ANS2.TXT");
if(!ofs)
{
cout<<"cannot open file ANS2.TXT.\n";
exit(1);
}

switch(L)
{
case 2:
str = "1\n";
str +="1 0 1\n";
str +="2 0 2\n";

break;

case 3:
str = "1\n";
str +="1 0 1\n";
str +="2 1 3\n";
str +="3 0 3\n";

break;

case 4:
str = "1 2\n";
str +="1 0 1\n";
str +="2 0 2\n";
str +="3 1 4\n";
str +="4 0 4\n";

break;

case 5:
str = "1 2\n";
str +="1 0 1\n";
str +="2 0 2\n";
str +="3 2 5\n";
str +="4 1 5\n";
str +="5 0 5\n";

break;

case 6:
str = "1 4\n";
str +="1 0 1\n";
str +="2 4 6\n";
str +="3 1 4\n";
str +="4 0 4\n";
str +="5 1 6\n";
str +="6 0 6\n";

break;
}

print(str);
print(str, ofs);
ofs.close();

return;
}

S = 0;
while( (S+2)*(S+1)/2 < L)
++S;

a[0] = 0;
while(1)
{
a[S+1] = L;

// program will be terminated in do_find()
// once a soln is found.
do_find(1, 1, L-1);

++S;
}
}

bool isSoln()
{
int k;
int m;
int idx;

// unset flags
for (k=1; k<= L; ++k)
b[k] = 0;

// double loop to check if 1..L are filled in
for (k=0; k<= S; ++k) // O(L*S)
{
for (m = k+1; m <= S+1; ++m) // O(L*S*S)
{
idx = a[m] - a[k];

// if not set
if ( b[idx] == 0 )
{
b[idx] = 1; // set it
c[idx] = a[k]; // record values
d[idx] = a[m];
}
}
}

k = 1;
while ( k<=L && b[k] != 0 )
++k;

/**
If all flags are set, we have a soln; otherwise we don't.
*/
return (k == L+1);
}

[此贴子已经被作者于2007-7-3 9:22:55编辑过]

#139

天空の城2007-07-03 09:11

第4题:对于行之间的重排列，我没有都显示出来，因为每一个N阶拉丁方阵在行重排列后都有N!个!
------------5阶拉丁方阵------------
12345
21453
34512
45231
53124
------------5阶拉丁方阵------------
12345
21453
34521
45132
53214
------------5阶拉丁方阵------------
12345
21453
35124
43512
54231
------------5阶拉丁方阵------------
12345
21453
35214
43521
54132
------------5阶拉丁方阵------------
12345
21534
34152
45213
53421
------------5阶拉丁方阵------------
12345
21534
34251
45123
53412

....还有很多。。。代码在楼下。

#140

天空の城2007-07-03 09:12

#include <vector>
#include <iostream>
#include <algorithm>
#include <cassert>
#include <cmath>
using namespace std;

int XAND(int a,int b)
{
int result=0;
for(int i=0;;i++)
{
if(a%10==b%10)
result+=((a%10)*pow(10,i));
a/=10;
b/=10;
if(a==0||b==0)
break;
}
return result;
}
bool VALID(int *p,int num)
{
for(int i=0;i<num-1;i++)
for(int j=i+1;j<num;j++)
if(XAND(p[i],p[j])!=0)
return false;
return true;
}
bool VALID(const vector<int>&vi)
{
int num=vi.size();
assert(num>=2);
for(int i=0;i<num-1;i++)
for(int j=i+1;j<num;j++)
if(XAND(vi[i],vi[j])!=0)
return false;
return true;
}
int IntFromArray(int p[],int num)
{
int result=0;
for(int i=num-1;i>=0;i--)
result+=p[i]*pow(10,i);
return result;
}
void Print(const vector<int>& rem,int n)
{
cout<<"------------"<<n<<"阶拉丁方阵------------\n";
for(int i=0;i<rem.size();i++)
{
cout<<rem.at(i)<<endl;
}
}
int factional(int n)
{
if(n==0||n==1)return 1;
return factional(n-1)*n;
}
void Func(vector<int>&rem,const vector<int>& vi,int n,int start=0)
{
static int num=factional(n-1);
static int NUM=n*num;
for(int i=start;i<start+num;i++)
{
rem.push_back(vi[i]);
if(start+num==NUM)
{
if(VALID(rem))
Print(rem,n);
}
else Func(rem,vi,n,start+num);
rem.pop_back();
}
}

void LaTinN(int n)
{
assert(n<9&&n>2);
int *p=new int[n];
for(int i=0;i<n;i++)
p[i]=i+1;
vector<int> vi,rem;
vi.push_back(IntFromArray(p,n));
while(next_permutation(p,p+n))
{
vi.push_back(IntFromArray(p,n));
}
delete[]p;
sort(vi.begin(),vi.end());
Func(rem,vi,n);
}
void main()
{
LaTinN(5);
}

#141

HJin2007-07-03 11:03

/*---------------------------------------------------------------------------
File name: C76-58.cpp
Author: HJin
Created on: 7/2/2007 19:44:06
Environment: Windows XP Professional SP2 English +
Visual Studio 2005 v8.0.50727.762

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

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

58. 将7万元投资到A，B，C三项目上，其利润见下表：
投资额(万元)│ 1 2 3 4 5 6 7
──────┼────────────────────
项 A │0.11 0.13 0.15 0.24 0.24 0.30 0.35
B │0.12 0.16 0.21 0.25 0.25 0.29 0.34
目 C │0.08 0.12 0.20 0.26 0.26 0.30 0.35
如何分配投资额，使获得的利润最大。

Analysis:
---------------------------------------------------------------------------
Just use a double loop to search maximum for A[i] + B[j] + C[k]
such that i+j+k = 7.

Sample output:
---------------------------------------------------------------------------
0.53 = 0.11 + 0.16 + 0.26.
Plan is to invest 1 万元 for 项目 A, 2 万元 for 项目 B, 4 万元 for 项目 C.
maximum profit is 0.53
Press any key to continue . . .

Reference:

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

*/

#include <iostream>
using namespace std;

int main(int argc, char** argv)
{
int i;
int j;
int k;
int best_i;
int best_j;
int best_k;
float profit;
float max_profit = 0.0;

// data --- note that we added the first column for 0 investment
float A[] = {0.0, 0.11, 0.13, 0.15, 0.24, 0.24, 0.30, 0.35};
float B[] = {0.0, 0.12, 0.16, 0.21, 0.25, 0.25, 0.29, 0.34};
float C[] = {0.0, 0.08, 0.12, 0.20, 0.26, 0.26, 0.30, 0.35};

// double loop to search maximum for A[i] + B[j] + C[k]
// such that i+j+k = 7.
for(i=0; i<8; ++i)
{
for(j=0; j<=7-i; ++j)
{
profit = A[i];

profit += B[j];

k = 7-i-j;
if(k>=0)
{
profit += C[k];
}

if(max_profit < profit)
{
max_profit = profit;
best_i = i;
best_j = j;
best_k = k;
}
}
}

// outputs
cout<<max_profit<<" = "
<<A[best_i]<<" + "
<<B[best_j]<<" + "
<<C[best_k]<<".\n";

cout<<"Plan is to invest " <<best_i<<" 万元 for 项目 A, "
<<best_j<<" 万元 for 项目 B, "
<<best_k<<" 万元 for 项目 C.\n";
cout<<"maximum profit is "<<max_profit<<endl;

return 0;
}

#142

zkkpkk2007-07-03 11:33

/*
9. 四人玩火柴棍游戏，每一次都是三个人赢，一个人输。输的人要按赢者手中的火柴
数进行赔偿，即赢者手中有多少根火柴棍，输者就赔偿多少根。现知道玩过四次后，
每人恰好输过一次，而且每人手中都正好有１６根火柴。问此四人做游戏前手中各有
多少根火柴? 编程解决此问题。
*/
#include <iostream.h>

int main()
{
    int array[4] = {16, 16, 16, 16};
    int i=0, j=0;
    for(i=0;i<4;i++)
        for(j=0;j<4;j++)
            if(j != i)
            {
                array[j]/=2;
                array[i]+=array[j];
            }

    for(i=0;i<4;i++)
        cout<<\"第\"<<i+1<<\"个人有火柴：\"<<array[i]<<endl;
    return 0;
}

#143

cyzyh882007-07-03 14:22

晕啦!都看不懂啊!

#144

zkkpkk2007-07-03 16:32

以前玩过一个游戏叫幻想传说，里面有个开门的迷题

程序代码：

/*
13. 有N个硬币（N为偶数）正面朝上排成一排，每次将 N-1 个硬币翻过来放在原位
置，不断地重复上述过程，直到最后全部硬币翻成反面朝上为止。编程让计算机把
翻币的最简过程及翻币次数打印出来（用＊代表正面，O 代表反面）。
*/
#include <iostream.h>
#define N 4
char array[N];

void Display()
{
    for(int i=0;i<N;i++)
        cout<<array[i]<<'\t';
    cout<<endl;
}
int main()
{
    int i=0,j=0;

    for(i=0;i<N;i++)
        array[i]='*';

    for(i=0;i<N;i++)
    {
        for(j=0;j<N;j++)
            if(j!=i)
            {
                if(array[j]=='*')
                    array[j]='0';
                else
                    array[j]='*';
            }
        Display();
    }

return 0;
}

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

#145

aipb20072007-07-03 17:11

回复：（zkkpkk）以前玩过一个游戏叫幻想传说，里面有...

晕，起码给个输出啊！
你变来变去，别人看不到啊！

呵呵~

#146

zkkpkk2007-07-03 17:17

回复：（zkkpkk）以前玩过一个游戏叫幻想传说，里面有...

不好意思，忘记了，其实幻想里就是4个开关，踩一个其他3个就变状态，4个开关状态相反时门开，其实按顺序从头踩到尾门就开了

改了......

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

#147

HJin2007-07-03 18:57

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

/*---------------------------------------------------------------------------
File name: C76-57.cpp
Author: HJin (fish_sea_bird[at]yahoo.com)
Created on: 7/2/2007 19:44:06
Environment: Windows XP Professional SP2 English +
Visual Studio 2005 v8.0.50727.762

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

7/3/2007 03:57:07
-----------------------------------------------------------
added analysis and email address.

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

经典 76 道编程题之 57:

57. 某一印刷厂有六项加工任务，对印刷车间和装订车间所需时间见下表(时间单
位：天)
任务 │J1 J2 J3 J4 J5 J6
─────┼───────────────
印刷车间│ 3 12 5 2 9 11
装订车间│ 8 10 9 6 3 1
如何安排加工顺序，使加工时间最少。

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

We make the following assumptions:
(a) All 印刷 (printing) job has to be done before its correspondnig 装订
(assembly) job;
(b) There is no waiting time between printing jobs;
(c) there are some waiting time (possibly 0, or no) between two consecutive
assembly job --- either because all available assembly jobs have been
finished or because we have to wait for a printing job to finish.

a_1 .. a_n --- time for printing jobs;
b_1 .. b_n --- time for assembly jobs;
(a_i is associated with b_i)

Our goal is to find a permuatation j1..jn of 1..n such that the final assembly
time is least, when we perform the jobs in the order of J_{j1}, ..., J_{jn}.

Define two ararays:

d[i] --- minimum time to finish assembly jobs j1..ji, i=0, 1, ..., n,
where j0 means a dummy job which takes no time to finish.
d[0] = 0;

c[i] --- time to finish printing jobs j1..ji, i=0, 1, ..., n,
where j0 means a dummy job which takes no time to finish.
c[0] = 0.

Then for i>0, we have
c[i] = c[i-1] + a[ji],
(*) d[i] = min_{j \in {1..n} \ { j1..j_{i-1} } } max( d[i-1] + b[j], c[i-1] + a[j] + b[j] ).

Note that it is the min-max concept that makes this problem hard for an undergraduate.
See our implementation of the min-max function.

Sample output:
---------------------------------------------------------------------------

加工顺序 is J4-->J5-->J1-->J6-->J3-->J2.
加工时间最少 is 52.
Press any key to continue . . .

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

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

*/

#include <iostream>
using namespace std;
#define N 6
#define INFPos ~(1<<31)

#include "hjns.h"

int a[N] = {3, 12, 5, 2, 9, 11};
int b[N] = {8, 10, 9, 6, 3, 1};

/**
Is job j used?
*/
int used[N];

/**
Total time to finish printing jobs j1 to ji,
i=0, 1, ..., N.

c[0] = 0.
*/
int c[N+1];

int jobIndex[N];

/**
Minimum time to finish assembly jobs j1 to ji,
i =0, 1, ..., N

d[0] = 0.
*/
int d[N+1];

/** Implement the min-max concept defined in equation (*).

Time complexity is O(N^2).
*/
void minmax();

void printOptSoln();

inline int max2(int a, int b);

int main(int argc, char** argv)
{
int i;

c[0] = 0;
d[0] = 0;

// all jobs are not used.
for(i=0; i<N; ++i)
used[i] = 0;

minmax();

return 0;
}

void minmax()
{
/** i = number of jobs finished so far

Remeber that we have a dummy job J_{j0} for both the printing jobs
and the assembly jobs, which takes no time to finish.
*/
int i = 1; // The dummy job is finished.

int j;
int thisMax; // current max
int minMax; // the min-max

while(i<N+1)
{
minMax = INFPos; // set it to +\inf

for(j=0; j<N; ++j)
{
// if the job is not used
if( used[j] == 0 )
{
// get maximum of the two numbers
thisMax = max2(d[i-1] + b[j], c[i-1] + a[j] + b[j]);

// keep track of min-max and the job index
if( minMax > thisMax)
{
minMax = thisMax;
jobIndex[i-1] = j;
}
}
}

used[ jobIndex[i-1] ] = 1; // used one job
d[i] = minMax; // the assembly time
c[i] = c[i-1] + a[ jobIndex[i-1] ]; // the printing time

++i; // go to next job
}

// print optimal solution
printOptSoln();
}

inline int max2(int a, int b)
{
return (a>b) ? a : b;
}

void printOptSoln()
{
int i;

// add one to each job index
for(i=0; i<N; ++i)
{
++jobIndex[i];
}

cout<<"加工顺序 is ";
for(i=0; i<N-1; ++i)
{
cout<<"J"<<jobIndex[i]<<"-->";
}
cout<<"J"<<jobIndex[i]<<"."<<endl;

cout<<"加工时间最少 is "<<d[N]<<"."<<endl;
}

#148

HJin2007-07-03 20:09

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

/*---------------------------------------------------------------------------
File name: C76-53.cpp
Author: HJin (fish_sea_bird[at]yahoo.com)
Created on: 7/2/2007 19:44:06
Environment: Windows XP Professional SP2 English +
Visual Studio 2005 v8.0.50727.762

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

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

经典 76 道编程题之 53:

53. (工作安排问题) 现有 N (N<=8) 件工作, 分别由 N 个人完成, 每人都完成一
件,且只完成一件, 每人完成不同工作的时间不同. 试设计一种分配工作方案, 使
完成 N 件工作所需的总时间最少.

原始数据由文本文件 EXAM1.TXT 给出, 其格式如下:
第 1 行: 工作任务数(N)
第 2 -- N+1 行: 第 i+1 行为第 i 个人完成各件工作所需的时间. 以上各数
均为不超过 1000 的正整数.
计算结果可直接在屏幕上输出: 第一行为工作分配方案, 共 N 组, 每组数据的
形式为 a-b, 其中 a 为工作人员编号, b 为他应完成的工作序号.
例: 设 EXAM1.TXT 的数据为:

4
2 15 13 4
10 4 14 15
9 14 16 13
7 8 11 9
对此, 一个正确的输出可以是
1-4, 2-2, 3-1, 4-3
TOTAL=28

Analysis:
---------------------------------------------------------------------------
For N small, we can just check all N! permuations of 1..N to tell which
permuatation j1..jN gives the minimum for

a[1, j1] + a[2, j2] + ... + a[N, jN].

This approach is obviously O(N!), or exponential growth by the famous
Stirling's formula for N!.

For N large, one should, in general, use a dynamic programming alogrithm
to solve it (not shown in this file).

Sample output:
---------------------------------------------------------------------------

EXAM1.TXT 的数据为:
4
2 15 13 4
10 4 14 15
9 14 16 13
7 8 11 9
对此, 一个正确的输出可以是
1-4, 2-2, 3-1, 4-3
TOTAL=28
Press any key to continue . . .

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

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

*/

#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

/**
2d array allocation and deallocation.
*/
template <class T>
T** new2d(int row, int col);

template <class T>
void delete2d(T** arr2d, int row);

int main(int argc, char** argv)
{
int N;
int i;
int j;
int* b;
int* minIndex;
int** a;
ifstream ifs("EXAM1.TXT");
int temp;
int min =0;

if(!ifs)
{
cout<<"caanot open file EXAM1.TXT.\n";
exit(0);
}
ifs>>N; // read in N

// allocate memory
b = new int[N];
minIndex = new int[N];
a= new2d<int>(N, N);

// read data in
for(i=0; i<N; ++i)
{
for(j=0; j<N; ++j)
{
ifs>>a[i][j];
}
}
ifs.close();

cout<<"EXAM1.TXT 的数据为:\n";
cout<<N<<endl;
for(i=0; i<N; ++i)
{
for(j=0; j<N; ++j)
{
cout<<a[i][j]<<" ";
}
cout<<endl;
}

for(i=0; i<N; ++i)
{
b[i] = i;
minIndex[i] = b[i];
}

for(i = 0; i<N; ++i)
{
min += a[i][ b[i] ];
}

// check all permuations.
while (next_permutation(b, b+N) )
{
temp = 0;
for(i = 0; i<N; ++i)
{
temp += a[i][ b[i] ];
}

if(min > temp)
{
min = temp;
for(i=0; i<N; ++i)
{
minIndex[i] = b[i];
}
}
}

// print results
cout<<"对此, 一个正确的输出可以是\n";
for(i=0; i<N-1; ++i)
{
cout<<i+1<<"-"<<minIndex[i]+1<<", ";
}
cout<<i+1<<"-"<<minIndex[i]+1<<"\n";

cout<<"TOTAL="<<min<<endl;

// free memory
delete [] b;
delete [] minIndex;
delete2d<int>(a, N);

return 0;
}

template <class T>
T** new2d(int row, int col)
{
T** arr2d = new T*[row];
for(int i=0; i<row; ++i)
arr2d[i] = new T[col];

return arr2d;
}

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

delete [] arr2d;
}

#149

HJin2007-07-04 07:34

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

/*---------------------------------------------------------------------------
File name: C76-22.cpp
Author: HJin (email: fish_sea_bird[at]yahoo.com)
Created on: 6/25/2007 04:45:37
Environment: Windows XP Professional SP2 English +
Visual Studio 2005 v8.0.50727.762

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

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

经典 76 道编程题之 22 :

22. 在一个４＊４的小方格（如图所示）中放置８个＊号，使得每行每列放且
仅放两个＊号。

┌─┬─┬─┬─┐
│＊│＊│ │ │
├─┼─┼─┼─┤
│＊│ │＊│ │
├─┼─┼─┼─┤
│ │＊│ │＊│
├─┼─┼─┼─┤
│ │ │＊│＊│
└─┴─┴─┴─┘

求出所有的基本解。

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

There are totally 6 (= 4 choose 2) combinations to put two ＊ and two blanks
on one row. Consider 1st row and 2nd row:
(a) 1st row is the same as 2nd row: in this case, 3rd row = 4th row, and we have
6*1*1 choices (first row 6, 2nd row 1, 3rd and 4th row 1);
(b) 1st row and 2nd row have exactly 1 ＊ on the same column (as shown in the
problem statement): in this case 3rd and 4th can have 2 choices, totally we have
6*4*2 choices (first row 6, 2nd row 4, 3rd and 4th row 2)
(c) 1st row and 2nd row have 0 ＊ on the same column: in this case, 3rd and
4th row can have 6 choices, totally we have
6*1*6 choices (first row 6, 2nd row 1, 3rd and 4th row 6).
All in all, we have
6*1*1 + 6*4*2 + 6*1*6 = 90
choice.

This is verified by our program.

Comment: this is not a smart analysis --- one should be able to not to divide
the problem into 3 cases.

Sample output:
---------------------------------------------------------------------------
(only the last 6 outputs are shown here. check the output file for all
solns.)

#85:
-----------------
＊＊
＊＊
＊＊
＊＊

#86:
-----------------
＊＊
＊＊
＊＊
＊＊

#87:
-----------------
＊＊
＊＊
＊＊
＊＊

#88:
-----------------
＊＊
＊＊
＊＊
＊＊

#89:
-----------------
＊＊
＊＊
＊＊
＊＊

#90:
-----------------
＊＊
＊＊
＊＊
＊＊
Press any key to continue . . .

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

1. 野比, 相当经典的76道编程自虐题分享.无答案 at
https://bbs.bc-cn.net/viewthread.php?tid=147853

*/

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

int g_allCombinations[6][4] = {
{1, 1, 0, 0},
{1, 0, 1, 0},
{1, 0, 0, 1},
{0, 1, 1, 0},
{0, 1, 0, 1},
{0, 0, 1, 1}
};

inline void copy(int*dest, int* src);
bool isValid(int (*a)[4]);

void print(int a[][4], int counter, std::ostream& os = cout);

int main(int argc, char** argv)
{
int i; // 1st row
int j; // 2nd row
int k; // 3rd row
int l; // 4th row
int counter = 0;
ofstream ofs("C76-22-Ans.txt");
if(!ofs)
{
cout<<"cannot open file C76-22-Ans.txt.\n";
exit(0);
}

int a[4][4];

for(i=0; i<6; ++i)
{
copy(a[0], g_allCombinations[i]);
for(j=0; j<6; ++j)
{
copy(a[1], g_allCombinations[j]);
for(k=0; k<6; ++k)
{
copy(a[2], g_allCombinations[k]);
for(l=0; l<6; ++l)
{
copy(a[3], g_allCombinations[l]);
if( isValid(a) )
{
++counter;

// print result
print(a, counter);
print(a, counter, ofs);
}
}
}
}
}

ofs.close();

return 0;
}

void copy(int*dest, int* src)
{
for(int i=0; i<4; ++i)
dest[i] = src[i];
}

bool isValid(int (*a)[4])
{
int i;
int j;
int sum;

/**
Check if we have two items in each column ---
our construction of the rows made sure that
each row has exactly two ＊s.
*/
for(j=0; j<4; ++j)
{
sum = 0;
for(i=0; i<4; ++i)
{
sum += a[i][j];
}
if(sum != 2)
return false;
}

return true;
}

void print(int a[][4], int counter, std::ostream& os)
{
os<<"\n#"<<counter<<":\n";
os<<"-----------------\n";
for(int i=0; i<4; ++i)
{
for(int j=0; j<4; ++j)
{
//os<<a[i][j]<< " ";
if(a[i][j] == 1)
{
os<<"＊";
}
else
{
os<<" ";
}
}
os<<endl;
}
}

#150

zkkpkk2007-07-04 10:53

临放假前最后一道了，学校流量用尽，在网吧做的，对于Hjin我服了，4*4方格那道做一半卡了，上来一看Hjin都发了，7月6号走人个把星期不会在上你们继续享受算法的乐趣，不过Hjin我还会回来的！

程序代码：

/*
43. 对于次数很高，但项目很少的多项式，可用链表来表示。
例如：X^1000－76*X^76＋3*X^3－7可表示为

  ┌─┬──┬─┐  ┌──┬─┬─┐   ┌─┬─┬─┐  ┌─┬─┬──┐
  │1 │1000│  ┼→│-76 │78│  ┼→ │3 │3 │  ┼→│-7│0 │ NIL│
  └─┴──┴─┘  └──┴─┴─┘   └─┴─┴─┘  └─┴─┴──┘

在此方式下，编程完成两个多项式的加法与乘法。
*/
#include <iostream.h>

class Node
{
private:
    int cof;
    int exp;
    Node* next;
public:
    //用默认值初始化
    Node()
    {
        cof=0;
        exp=0;
        next=NULL;
    }
    //用给定值初始化
    Node(int cof,int exp)
    {
        this->cof=cof;
        this->exp=exp;
        next=NULL;
    }
    //建立多项式
    Node* CreateLink(Node* head,int m);
    //取头节点
    Node* GetHead(Node* head);
    //多项式加法
    Node* AddNode(Node* head1,Node* head2);
    //乘法
    Node* MultiNode(Node* head1,Node* head2,Node* head3);
    //输出
    void Display(Node* head);
};

/*取头节点*/
Node* Node::GetHead(Node* head)
{
return head;
}

/*输出多项式*/
void Node::Display(Node* head)
{
    Node* temp=head;
    while(temp!=NULL)
    {
        temp=temp->next;
        if(temp->exp==0)        //处理指数为0的情况
            cout<<temp->cof<<\"  \";
        else
            cout<<temp->cof<<\"*X^\"<<temp->exp<<\"  \";
    }
    cout<<endl;
}

/*建立链表，m为节点数*/
Node* Node::CreateLink(Node* head,int m)
{
    Node *p=head;
    cout<<\"Input cof and exp\"<<endl;
    for(int i=1;i<=m;i++)
    {
        int cof,exp;
        cout<<\"cof:\";
        cin>>cof;
        cout<<\"exp\";
        cin>>exp;
        Node* newnode=new Node;
        newnode->cof=cof;
        newnode->exp=exp;
        newnode->next=p->next;
        p->next=newnode;
        p=newnode;
    }
    return head;
}

/*多项式加法*/
Node* Node::AddNode(Node* head1,Node* head2)
{
    Node* ha=GetHead(head1);
    Node* hb=GetHead(head2);
    Node *la=ha,*lb=hb;
    Node *qa=la->next;
    Node *qb=lb->next;

    while(qa!=NULL && qb!=NULL)        //pa,pb不为空指数比较
    {
        if(qa->exp > qb->exp)        //如果qa指数大
        {
            la=qa;
            qa=qa->next;
        }
        if(qa->exp == qb->exp)        //如果指数相等
        {
            int sum=qa->cof+qb->cof;
            if(sum!=0)        //系数不为0
            {
                /*修改系数值*/
                qa->cof=sum;
                la=qa;
                qa=qa->next;
                lb->next=qb->next;
                delete qb;
                qb=lb->next;
            }
            else        //系数为0
            {
                /*删除多项式pa中的当前节点*/
                la->next=qa->next;
                delete qa;
                qa=la->next;
                lb->next=qb->next;
                delete qb;
                qb=lb->next;
            }
        }
        if(qa->exp < qb->exp)        //如果pb指数大
        {
            /*qb在前*/
            lb->next=qb->next;
            la->next=qb;
            qb->next=qa;
            la=qb;
            qb=lb->next;
        }
    }
    if(qb!=NULL)
        la->next=qb;
    delete lb;
    return ha;
}
/*乘法*/
Node* Node::MultiNode(Node* head1,Node* head2,Node* head3)
{
    Node* ha=GetHead(head1);
    Node* hb=GetHead(head2);
    Node* hc=GetHead(head3);
    Node *la=ha,*lb=hb,*tmp=hc;
    Node* qa=la->next;
    Node* qb=lb->next;

    while(qa!=NULL)
    {
        while(qb!=NULL)
        {
            /*系数相乘指数相加*/
            int sumc=qa->cof*qb->cof;
            int sume=qa->exp+qb->exp;
            /*结果存入新的节点*/
            Node* newnode=new Node;
            newnode->cof=sumc;
            newnode->exp=sume;
            newnode->next=tmp->next;
            tmp->next=newnode;
            tmp=newnode;
            qb=qb->next;
        }
        /*qb回到第一个qa指向下一个*/
        qb=lb->next;
        qa=qa->next;
    }
    delete tmp;
    return hc;
}

int main()
{
    Node* head1=new Node;
    Node* head2=new Node;
    Node* head3=new Node;
    Node n1;
    n1.CreateLink(head1,2);
    cout<<\"Ploy1:\";
    n1.Display(head1);
    n1.CreateLink(head2,2);
    cout<<\"Ploy2:\";
    n1.AddNode(head1,head2);
    cout<<\"Ploy1 add ploy2:\";
    n1.Display(head1);
    n1.MultiNode(head1,head2,head3);
    cout<<\"Ploy1 mut ploy2:\";
    n1.Display(head3);
    return 0;
}

[此贴子已经被作者于2007-7-4 19:18:04编辑过]

#151

aipb20072007-07-04 10:59

回复：（zkkpkk）临放假前最后一道了，学校流量用尽，...

放假也要经常来啊！

（*_*）