/*---------------------------------------------------------------------------
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)
{
int sum=0;
cout<<"total number of face values are "<<testMN_Total(3, 6)<<endl;
return 0;
}
