/*---------------------------------------------------------------------------
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++练习题
http://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;
}

/*
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;
}

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

程序代码：

/*
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编辑过]

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

/*---------------------------------------------------------------------------
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++练习题
http://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;
}

/*---------------------------------------------------------------------------
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++练习题
http://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;
}

/*---------------------------------------------------------------------------
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
http://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;
}
}

临放假前最后一道了，学校流量用尽，在网吧做的，对于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编辑过]