不管怎么说, 赞一个先

都是牛人!
呵呵

顶　看看先

[此贴子已经被作者于2007-6-17 23:37:46编辑过]

NO.19:
Greedy Algorithms;

Analysis：
Remove item j from this load, the remaining load must be the

most valuable load weighing at most max - weight(j) that we can take from the n - 1 original items excluding j.
To solve the problem, we first compute the value per pound

value(i)/weight(i) for each item. Obeying a greedy strategy, we begins

by taking as much as possible of the item with the greatest value per

pound. If the supply of that item is exhausted and we can still carry

more, we takes as much as possible of the item with the next greatest

value per pound, and so forth until we can't carry any more. Thus, by

sorting the items by value per pound, the greedy algorithm runs in O(n

lg n) time.

#include<iostream>
using namespace std;
struct information
{
float price;
float weight;
float number;
int serial_number;
};
void sort_ascending(information good[],int n)// according to the ratio of price and weight,sort_ascending arrange
{
int i,j;
for(j=2;j<=n;j++)
{
good[0]=good[j];
i=j-1;
while(good[0].price>good[i].price)
{
good[i+1]=good[i];
i--;
}
good[i+1]=good[0];
}

}
void backpack(information good[],float max,int n)
{
float left;
int i,j;
for(i=1;i<n;i++)
good[i].number=0;
left=max;
for(i=1;i<n;i++)
{
if(good[i].weight>left)
break;
good[i].number=1;
left=left-good[i].weight;
}
if(i<=n)
good[i].number=left/good[i].weight;

for(j=2;j<n;j++) //according to good'serial number,from high to low
{
good[0]=good[j];
i=j-1;
while(good[0].serial_number<good[i].serial_number)
{
good[i+1]=good[i];
i--;
}
good[i+1]=good[0];
}
cout<<"The most excellent result is:"<<endl;
for(i=1;i<=n;i++)
{
cout<<"The "<<i<<"th good should input: ";
cout<<good[i].number<<endl;
}
}
int main()
{
int i,j;
int n;
float max;
information *good;
while(j)
{
cout<<"Please input goods's number: "<<endl;
cin>>n;
good=new struct information [n+1];
cout<<"Please input the max of goods's capability"<<endl;
cin>>max;
cout<<endl;
int i;
for(i=1;i<=n;i++)
{
good[i].serial_number=i;
cout<<"Please input the "<<i<<"th goods'weight:"<<endl;
cin>>good[i].weight;
cout<<"Please input the "<<i<<"th goods'price:"<<endl;
cin>>good[i].price;
good[i].price=good[i].price/good[i].weight;
cout<<endl;
}
sort_ascending(good,n);
backpack(good,max,n);

break;
}
system("pause");
return 0;
}

[此贴子已经被作者于2007-6-19 11:31:34编辑过]

//第16题代码；
//完全是按顺序编写的，不带技术含量的，也不知道是否符合题意，呵呵

#include<iostream>
using namespace std;
int main()
{
int result;
cout << "第一次：称 abc和def"<<endl;
cout << "输入称量结果(平衡输入0;左重输入1;右重输入2):";
cin >> result;
if (result==0) //第一次称，平衡的情况
{
cout <<"第二次：称 a和g"<<endl;
cout << "输入称量结果(平衡输入0;左重输入1;右重输入2):";
cin >> result;
if (result==0)
{
cout <<"第三次：称 a和h"<<endl;
cout << "输入称量结果(左重输入1;右重输入2):"; //此时不可能平衡
cin >> result;
if (result==1)
{
cout <<"结果: h 偏轻"<<endl;
}
else
{
cout <<"结果: h 偏重"<<endl;
}
}
else if (result==1)
{
cout <<"结果: g 偏轻"<<endl;
}
else
{
cout <<"结果: g 偏重"<<endl;
}
}
else if (result==1) //第一次称，左重的情况
{
cout <<"第二次：称 cde和fgh"<<endl;
cout << "输入称量结果(平衡输入0;左重输入1;右重输入2):";
cin >> result;
if (result==0)
{
cout <<"第三次：称 a和b"<<endl;
cout << "输入称量结果(左重输入1;右重输入2):"; //此时不可能平衡
cin >> result;
if (result==1)
{
cout <<"结果: a 偏重"<<endl;
}
else
{
cout <<"结果: b 偏重"<<endl;
}
}
else if (result==1) //第二次称，左重的情况
{
cout <<"第三次：称 a和c"<<endl;
cout << "输入称量结果(平衡输入0;右重输入2):"; //此时不可能左重
cin >> result;
if (result==0)
{
cout <<"结果: f 偏轻"<<endl;
}
else
{
cout <<"结果: c 偏重"<<endl;
}
}
else //第二次称，右重的情况
{
cout <<"第三次：称 a和d"<<endl;
cout << "输入称量结果(平衡输入0;左重输入1):"; //此时不可能右重
cin >> result;
if (result==0)
{
cout <<"结果: e 偏轻"<<endl;
}
else
{
cout <<"结果: d 偏轻"<<endl;
}
}
}
else //第一次称，右重的情况
{
cout <<"第二次：称 cde和fgh"<<endl;
cout << "输入称量结果(平衡输入0;左重输入1;右重输入2):";
cin >> result;
if (result==0)
{
cout <<"第三次：称 a和b"<<endl;
cout << "输入称量结果(左重输入1;右重输入2):"; //此时不可能平衡
cin >> result;
if (result==1)
{
cout <<"结果: b 偏轻"<<endl;
}
else
{
cout <<"结果: a 偏轻"<<endl;
}
}
else if (result==2) //第二次称，右重的情况
{
cout <<"第三次：称 a和c"<<endl;
cout << "输入称量结果(平衡输入0;左重输入1):"; //此时不可能右重
cin >> result;
if (result==0)
{
cout <<"结果: f 偏重"<<endl;
}
else
{
cout <<"结果: c 偏轻"<<endl;
}
}
else //第二次称，左重的情况
{
cout <<"第三次：称 a和d"<<endl;
cout << "输入称量结果(平衡输入0;右重输入2):"; //此时不可能左重
cin >> result;
if (result==0)
{
cout <<"结果: e 偏重"<<endl;
}
else
{
cout <<"结果: d 偏重"<<endl;
}
}
}
return 0;
}

11. 巧排数字。将１、２、．．．、２０这２０个数排成一排，使得相邻的两个数之
和为一个素数，且首尾两数字之和也为一个素数。编程打印出所有的排法。
--------------------------------------------------------------------------------------
[CODE]/*
title : NO.11
author : aipb2007
date : 2007-06-18

analysis :
It's problem like "N queen",both use the algorithm of recursion and backtracking.
Use an array to store the solution.

design :
//print one solution
print(int a[],int n);
//check an integer is already in the array
bool is_in(int a[],int n,int in);
//check a number is a prime number
bool is_prime(double num);
//recursive function for backtracking
void solution(int a[],int n,int k);

in addition:
The questions has a problem, it's so many solution for 20 numbers.By using this
way,the computer will use a large time to do this,maybe can not.
However,maybe my program has a low efficiency.
So I change the number to 8,just for testing.

sample output :
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2
2 1 4 7 6 5 8 3
2 1 6 7 4 3 8 5
2 3 8 5 6 7 4 1
2 5 8 3 4 7 6 1
3 2 1 4 7 6 5 8
3 4 7 6 1 2 5 8
3 8 5 2 1 6 7 4
3 8 5 6 7 4 1 2
4 1 2 3 8 5 6 7
4 3 8 5 2 1 6 7
4 7 6 1 2 5 8 3
4 7 6 5 8 3 2 1
5 2 1 6 7 4 3 8
5 6 7 4 1 2 3 8
5 8 3 2 1 4 7 6
5 8 3 4 7 6 1 2
6 1 2 5 8 3 4 7
6 5 8 3 2 1 4 7
6 7 4 1 2 3 8 5
6 7 4 3 8 5 2 1
7 4 1 2 3 8 5 6
7 4 3 8 5 2 1 6
7 6 1 2 5 8 3 4
7 6 5 8 3 2 1 4
8 3 2 1 4 7 6 5
8 3 4 7 6 1 2 5
8 5 2 1 6 7 4 3
8 5 6 7 4 1 2 3
*/


#include <iostream>
#include <cmath>
using namespace std;
void print(int a[],int n){
for (int i = 0; i < n;++i)
cout << a[i] << " ";
cout << endl;
}

bool is_in(int a[],int n,int in){
for (int i = 0;i < n;++i)
if (in == a[i])
return true;
return false;
}

bool is_prime(double num){
double d = sqrt(num);
for (int i = 2;i <= (int)d;++i)
if ((int)num % i == 0)
return false;
return true;
}

void solution(int a[],int n,int k){
if (k == n && is_prime(a[k-2]+a[k-1]) && is_prime(a[0]+a[k-1]))
print(a,n);
else if (k < 2 || is_prime(a[k-2]+a[k-1])){
for (int i = 1;i <= n;++i)
if (!is_in(a,k,i)){
a[k] = i;
solution(a,n,k+1);
}
}
}

int main(){
int a[8];
solution(a,8,0);
}[/CODE]

[此贴子已经被作者于2007-6-18 19:27:26编辑过]

好多题看不懂拉，各位大大指点一下

/*---------------------------------------------------------------------------
File name: C76-75.cpp
Author: HJin
Date: 6/18/2007

6/18/2007
-----------------------------------------------------------
1. Refine the analysis: provide optimal substructure and the
recurrence formula for c[p].

C76-75.cpp --- the cpp source file for solving the 75th of the 76
classical C/C++ problems.

经典 76 道编程题 之 75:

75. (钱币系统问题) 某钱币系统由 k (k≤20) 种硬币组成, 币值依次为 a[1],
a[2],...,a[k], 其中 a[i] (i=1,2,...,k) 为互不相同的正整数, 且依降序排列,
a[1]≤200. 给定某整数币值 n(n≤3000), 要求用最少枚数的硬币表示这个币值.
输入: 用文件输入已知数据, 格式为:
第 1 行: k (硬币种数)
第 2 行: a[1] a[2] ... a[k] (各币值用空格隔开,已按降序排列好)
第 3 行: n (给定的币值)
输出: 直接在屏幕上输出结果. 如果该钱币系统无法表示币值 n,应输出'No',
否则按以下格式输出:
第 1 行: 最少钱币枚数 r.
第 2 行: 输出若干形如 m*n 的表达式, m 为币值, n为使用该币值的枚数.
各式第 2 个因子之和应等于 r, 各式乘积之和应等于 n.
例: 设 (a[1],a[2],a[3])=(5,2,1), n=12, 则应输出
3
5*2 2*1.

Analysis:

1. If 1 is in the set { a[1], a[2], ..., a[k] }, then we can change
any number n in at most n cions (since n = 1*n);

2. There is some set { a[1], a[2], ..., a[k] } such that this coin
changing problem can be solved by a greedy algorithm. For exmaple,

{5, 2, 1}

is such a set. And there exists a set { a[1], a[2], ..., a[k] }
such that the greedy algorithm does not give an optimal soln. For
example,

{5, 4, 1}

is such a set: 8 = 5*1 + 1*3 is the greedy soln, which needs 4 cions,
whereas 8 = 4*2 tells us that we can use just 2 coins.

3. A dynamic programming algorithm exists for any set. This needs some
understanding of the topic. Cormen's book is a wonderful reference.

4. This is really a classical and an interesting problem and a lot of
references exist. Just google for "coin changing problem, dynamic programming".

5. This problem needs more analysis than programming efforts. A complete
soln of this problem needs to describe (and prove) the optimal substructure,
which we omitted.

6. Our soln does NOT fulfil the requirements described in the problem
statement.

7. The optimal substructure:

Write n = m + (n-m). Then the left half of an optimal soln for n must
be an optimal soln for m, the right half of the optimal soln for n must
be an optimal soln for n-m.

8. Let c[p] be the minimum number of coins to make change for n, then

c[p] = 0, if p = 0;
= 1 + min { 1 + c[ p-a[i] ]: a[i] <= p}, if p> 0

Sample output:

n=0, No
n=1, No
n=2, No
n=3, No
n=4, No
n=5, No
n=6, No
n=7, r=1: 7*1
n=8, No
n=9, No
n=10, No
n=11, No
n=12, No
n=13, No
n=14, r=2: 7*2
n=15, r=1: 15*1
n=16, No
n=17, No
n=18, No
n=19, No
n=20, No
n=21, r=3: 7*3
n=22, r=2: 15*1 7*1
n=23, No
n=24, No
n=25, No
n=26, No
n=27, No
n=28, r=4: 7*4
n=29, r=3: 15*1 7*2
n=30, r=2: 15*2
n=31, r=1: 31*1
n=32, No
n=33, No
n=34, No
n=35, r=5: 7*5
n=36, r=4: 15*1 7*3
n=37, r=3: 15*2 7*1
n=38, r=2: 31*1 7*1
n=39, No
n=40, No
n=41, No
n=42, r=6: 7*6
n=43, r=5: 15*1 7*4
n=44, r=4: 15*2 7*2
n=45, r=3: 15*3
n=46, r=2: 15*1 31*1
n=47, No
n=48, No
n=49, r=7: 7*7
n=50, r=6: 15*1 7*5
n=51, r=5: 15*2 7*3
n=52, r=4: 15*3 7*1
n=53, r=3: 15*1 31*1 7*1
n=54, No
n=55, No
n=56, r=8: 7*8
n=57, r=7: 15*1 7*6
n=58, r=6: 15*2 7*4
n=59, r=5: 15*3 7*2
n=60, r=4: 15*4
n=61, r=3: 15*2 31*1
n=62, r=2: 31*2
n=63, r=9: 7*9
n=64, r=8: 15*1 7*7
n=65, r=7: 15*2 7*5
n=66, r=6: 15*3 7*3
n=67, r=5: 15*4 7*1
n=68, r=4: 15*2 31*1 7*1
n=69, r=3: 31*2 7*1
n=70, r=10: 7*10
n=71, r=9: 15*1 7*8
n=72, r=8: 15*2 7*6
n=73, r=7: 15*3 7*4
n=74, r=6: 15*4 7*2
n=75, r=5: 15*5
n=76, r=4: 15*3 31*1
n=77, r=3: 15*1 31*2
n=78, r=10: 15*1 7*9
n=79, r=9: 15*2 7*7
n=80, r=8: 15*3 7*5
n=81, r=7: 15*4 7*3
n=82, r=6: 15*5 7*1
n=83, r=5: 15*3 31*1 7*1
n=84, r=4: 15*1 31*2 7*1
n=85, r=11: 15*1 7*10
n=86, r=10: 15*2 7*8
n=87, r=9: 15*3 7*6
n=88, r=8: 15*4 7*4
n=89, r=7: 15*5 7*2
n=90, r=6: 15*6
n=91, r=5: 15*4 31*1
n=92, r=4: 15*2 31*2
n=93, r=3: 31*3
n=94, r=10: 15*3 7*7
n=95, r=9: 15*4 7*5
n=96, r=8: 15*5 7*3
n=97, r=7: 15*6 7*1
n=98, r=6: 15*4 31*1 7*1
n=99, r=5: 15*2 31*2 7*1
Press any key to continue . . .

Reference:
1. Thomas H. Cormen, introduction to algorithms.

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

#include <iostream>
#define INFPOS ~(1<<31) // (2^31-1)
#define DIM(x) (sizeof( (x) ) / sizeof( (x)[0] ))
using namespace std;

/**
@param a --- the array { a[1], a[2], ..., a[k] }. It does not
need to in decreasing order.
@param k --- number of coins
@param n --- the target number we want to make change
@return --- returns the minimum (positive) number of coins needed
to make a successful change; or -1 if the money system
cannot make the change.

Space complexity is Theta(n+k) --- there is a version of dynamic
programming algorithm which uses Theta(n*k) space. Obviously,
our version beats that version.
Time complexity is Theta(n * k).

Note that our algorithm does not require the set to be sorted beforehand.
*/
int change(int *a, int k, int n, bool print= true);

/**
print the optimal soln.
*/
int makeChange(int *a, int k, int n, int* b, bool print);

int main(int argc, char** argv)
{
//int a[] = {5, 4, 3};
int a[] = {15, 31, 7};
int k = DIM(a);
int n;
int res;

// test #1
for(n=0; n<100; ++n)
change(a, k, n);

// test #2
//for(n=40; n<80; ++n)
//{
// res = change(a, k, n, false);
// if(res == -1)
// cout<<n<<endl;
//}

return 0;
}

int change(int *a, int k, int n, bool print)
{
/**
c --- c[i] stores soln for n = i. If there is no soln for n=i,
then stores INFPOS;
s --- s[i] stores the index of the first coin for n=i. If there is
no soln for n =i, then stores INFPOS;
b --- b[j] stores the number of cions for the soln.
*/

int* c = new int[n+1];
int* s = new int[n+1];
int* b = new int[k];
int coinIndex=INFPOS;
int n2 = n;
int min;
int i;
int p;
int temp;

for(i=0; i<k; ++i)
b[i] = 0;

c[0] = 0; // n=0 needs zero coins to make
s[0] = INFPOS; // no coins can be used for n = zero

for(p=1; p<=n; ++p) // for face value 1 to n
{
min = INFPOS; // +\inf
for(i=0; i<k; ++i) // loop over the set of coins
{
if(a[i] <= p)
{
// temp implements the relation: 1 + +\inf = +\inf
temp = (c[p-a[i]] == INFPOS ? INFPOS : 1 + c[p-a[i]]);
if (min > temp )
{
min = temp; // keeps the local minimum
coinIndex = i; // select coin i
}
}
}

c[p] = min; // keeps the global min (the soln for n=p)
s[p] = coinIndex;
}

/**
build number of cions for each a[i] and store it in b[i]
*/
while(n2>0)
{
if( s[n2]>=0 && s[n2] <k )
++b[s[n2]];

n2 -= a[s[n2]];
}

// reuse n2 to keep a value
n2 = makeChange(a, k, n, b, print);

delete [] c;
delete [] s;
delete [] b;

return n2;
}

int makeChange(int *a, int k, int n, int* b, bool print)
{
int i;
int r=0;
int sum = 0;

if(print)
cout<<"n="<<n;

/**
calculate r --- the total number of cions for n
*/
for(i=0; i<k; ++i)
{
r+= b[i];
sum += b[i] * a[i];
}

/**
If the sum is not n, then there are no solns.
And treat the case n=0 as there are no solns.
*/
if (sum != n || n<1)
{
if(print)
cout<<", No"<<endl;
return -1;
}

if(print)
cout<<", r="<<r<<":\t";
for(i=0; i<k; ++i)
{
if( b[i] > 0 )
{
if(print)
cout<<a[i]<<"*"<<b[i]<<" ";
}
}

if(print)
cout<<endl;

return r;
}

[此贴子已经被作者于2007-6-19 3:01:51编辑过]

/*---------------------------------------------------------------------------
File name: C76-49.cpp
Author: HJin
Date: 6/16/2007

C76-49.cpp --- the cpp source file for solving the 49th of the 76
classical C/C++ problems.

经典 76 道编程自虐题 之 49:

49. 有面值为 M..N 的邮票各一枚，共能拼出多少不同的面额。

Analysis:

Let

y = x_M a[M] + x_{M+1} a[M+1] + ... + x_{N} a[N],

where

a[j] = j,
x_j is either 0 or 1

for M <= j <= N. x_j = 0 means the jth item (a[j])
is not picked in the sum; x_j = 1 means the jth item
is picked in the sum. Thus, we have 2^{N-M+1} possible
sums, of which some may repeat.

Our task is to count how many sums are distinct among these
2^{N-M+1} possibilites.

The following algorithms all run in O(2^{N-M+1}) time. A better
approach would be to apply some dynamic programming techniques,
which could give us polynomial running time.

Sample output:

1 3
2 4
3 5
4 6
5 7
6 8
7 9
8 10
9 11
10 12
11 13
12 14
13 15
14 18
total number of face values are 14
Press any key to continue . . .

Reference:

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

*/

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

/**
This function computes the result for M=1 and N.
*/
void test1N(int N, int& sum)
{
static int count=0; // counter

if(N==0)
{
++count;
cout<<count<<"\t"<<sum<<endl;
return;
}
else
{
/**
a[N] is not picked.
*/
int temp = sum; // remember previous sum
test1N(N-1, sum);

/**
a[N] is picked.
*/
sum = temp; // restore previous sum
sum += N;
test1N(N-1, sum);
}
}

/**
This function computes the result for M and N.
*/
void testMN(int M, int N, int& sum)
{
static int count=0; // counter

if(N==M-1)
{
++count;
cout<<count<<"\t"<<sum<<endl;
return;
}
else
{
int temp = sum;
testMN(M, N-1, sum);

sum = temp;
sum += N;
testMN(M, N-1, sum);
}
}

/**
This function computes the result for M and N and
put the sums in a set.
*/
void testMN(int M, int N, int& sum, set<int>& s)
{
if(N==M-1)
{
s.insert(sum);
return;
}
else
{
int temp = sum;
testMN(M, N-1, sum, s);

sum = temp;
sum += N;
testMN(M, N-1, sum, s);
}
}

/**
This function wraps the testMN function and returns
the total number of different sums.
*/
int testMN_Total(int M, int N, bool print=true)
{
set<int> s;
int sum=0;
testMN(M, N, sum, s);
int counter = -1;

if(print)
{
for(set<int>::const_iterator iter = s.begin(); iter != s.end(); ++iter)
{
++counter;

/** get rid of the case in which all x[j] = 0; i.e.,
the case none of the stamps is picked.
*/
if(counter)
cout<<counter<<"\t"<<*iter<<endl;
}
}

return s.size()-1;
}

int main(int argc, char** argv)
{
//cout<<"total number of face values are "<<testMN_Total(3, 7)<<endl;
for(int i=0; i<10; ++i)
{
cout<<
testMN_Total(1, 1+i, false)<<"\t"<<
testMN_Total(2, 2+i, false)<<"\t"<<
testMN_Total(3, 3+i, false)<<"\t"<<
testMN_Total(4, 4+i, false)<<"\t"<<
testMN_Total(5, 5+i, false)<<"\t"<<
testMN_Total(6, 6+i, false)<<"\t"<<
testMN_Total(7, 7+i, false)<<"\t"<<
testMN_Total(8, 8+i, false)<<"\t"<<
testMN_Total(9, 9+i, false)<<"\t"<<
//testMN_Total(10, 10+i, false)<<"\t"<<
endl;
}

return 0;
}

HJin老兄, 你太XX了吧... 连下两程... 实在佩服..
不过49题main函数带上参数干嘛? 好像用不到命令行哦..