考考你,请你编程(转贴)

题目： 
一块40斤的大石头摔成恰好是整数重量的四块，恰好可称出1-40斤中所有整数的重量， 
问：这四块石头重量各是多少？ 
(这题不是问你怎么样去称， 
那只是要求求出满足条件的四块石头的重量。 
答案是唯一的：1，3，9，27 

举一个例子重26的 可以是：26+1=27 
左边为重物和重1的石头， 右边为重27的石头。 
1—40都可以称出！大家明白了题意吧，)

请大家写带吗吧 ！ 

10 个解决方案

#1

呵呵，这哪需要编程序！
n块石头称重的最大重量为：S(n)=(3^n-1)/2
第n块石头的重量为：M(n)=3^(n-1)

#2

将40变成2进制1001110010101010001110.....

不是40是400000000......也一样ok

#3

可以提示：
设四块石头为：a、b、c、d
则有条件：
a+b+c+d=40;1<a、b、c、d<40;
可的：
1<a<38 1<b<37 1<c<37 d=40-a-b-c;(条件一)
还有：
设z=1...40
a=z or b=z or c=z or d=z or a+b=z or a+z=b or b+z=a......
等条件作为判断

利用循环则可得到结果。条件太多到是真的。

#4

如何推出分割出3^n的结果。

我初步这么设想：
如果石头只能放在一边，也就是重量只能相加，那应该是分割成2^n；
设石头能放在k边，可以分割成（k+1）^n成立；
石头放在(k+1)边，证明分割成(k+2)^n成立；
证明：
    还没有想完全，等下班后再想，现在头来了。

#5

同意 huxianwei(飞狐)

#6

设解集是A,初始A = 空
1必须有add(A,1);
set A可以称出的最大重量是所有元素的和 = sigma_A
所以A中元素加上(2 * sigma_A + 1)的元素必然可以称出
0 ~ (sigma_A + (2 * sigma_A + 1))的重量
所以设最大重量是n
i = 1;
sigma_A = 1;
i = sigma_A * 2 + 1;
while (i < n)
{
add(A, i);//A中加入i
从新计算sigma_A;
i = sigma_A * 2 + 1;
}
if(sigma_A < n)
{
add(A, n);//A中加入n
}
else
{
printf("Perfect!\n");
}
显然n = 40,会输出Perfect!解集是A
OVER!

#7

不仅仅只适用于40哦

#8

#include "iostream.h"
#include "stack"
using namespace std;

void SplitStones(int m, int n,int *pStoneArray);
bool checkArray(const int &m, const int &n, const int *pStoneArray);
bool *value;
stack <int *> resultList;

int main(int argc, char* argv[])
{
　　　　int m = 40;
　　　　int n = 4;
　　　　int i;
　　　　int *pStoneArray = new int[n];
　　　　value = new bool[m+1];//第一个不要

　　　　SplitStones(m,n,pStoneArray);
　　　　delete pStoneArray;
　　　　if(resultList.empty())
　　　　{
　　　　　　　　cout << "无法分出这样的" << n <<"块石头。" << endl;
　　　　}else
　　　　{
　　　　　　　　cout << "分出的" << n << "块石头重量如下" << endl;
　　　　　　　　while(!resultList.empty())
　　　　　　　　{
　　　　　　　　　　　　pStoneArray = resultList.top();
　　　　　　　　　　　　for(i = 0; i< n; i++)
　　　　　　　　　　　　　　　　cout << pStoneArray[i] << "　";
　　　　　　　　　　　　cout << endl;
　　　　　　　　　　　　delete pStoneArray;
　　　　　　　　　　　　resultList.pop();
　　　　　　　　}
　　　　}
　　　　delete value;
　　　　return 0;
}

void SplitStones(int m, int n, int *pStoneArray)
//重为m的石头分为n块
//假设n块石头重量x1,x2,...xn,并有x1<=x2<=...<=xn;这样可以少循环几次。去掉重复结果。
{
　　　　int i;
　　　　static int *pStoneArraySaved = NULL;
　　　　static int nSaved;
　　　　static int mSaved;
　　　　if(m<1 || n<1 || m < n) return ;

　　　　if(pStoneArraySaved == NULL)//最外一层循环，初始化
　　　　{
　　　　　　　　pStoneArraySaved = pStoneArray;
　　　　　　　　nSaved = n;
　　　　　　　　mSaved = m;
　　　　　　　　if(n ==1)//特殊情况，一开始总共只有一个元素。
　　　　　　　　{
　　　　　　　　　　　　if(m!=1)//m!=1,n=1,无法分
　　　　　　　　　　　　　　　　return;
　　　　　　　　　　　　else//m=1,n=1
　　　　　　　　　　　　{
　　　　　　　　　　　　　　　　pStoneArraySaved[0]=1;
　　　　　　　　　　　　　　　　pStoneArray = new int[nSaved];
　　　　　　　　　　　　　　　　for(i=0;i<nSaved;i++)
　　　　　　　　　　　　　　　　　　　　pStoneArray[i] = pStoneArraySaved[i];
　　　　　　　　　　　　　　　　resultList.push(pStoneArray);
　　　　　　　　　　　　　　　　return;
　　　　　　　　　　　　}
　　　　　　　　}
　　　　}

　　　　if(n ==1)//最里面一层循环
　　　　{
　　　　　　　　pStoneArray[0] = m;
　　　　　　　　if(pStoneArraySaved[nSaved -2] > pStoneArray[0])//前一个数值不能大于后一个数值。
　　　　　　　　　　　　return;
　　　　　　　　if(checkArray(mSaved, nSaved, pStoneArraySaved))
　　　　　　　　{
　　　　　　　　　　　　pStoneArray = new int[nSaved];
　　　　　　　　　　　　for(i=0;i<nSaved;i++)
　　　　　　　　　　　　　　　　pStoneArray[i] = pStoneArraySaved[i];
　　　　　　　　　　　　resultList.push(pStoneArray);
　　　　　　　　　　　　return;
　　　　　　　　}
　　　　　　　　return;
　　　　}

　　　　if(pStoneArraySaved == pStoneArray)//找到pStoneArray[0]的最小值，
　　　　　　　　i = 1;
　　　　else
　　　　　　　　i = pStoneArraySaved[pStoneArray-pStoneArraySaved-1];

　　　　for(pStoneArray[0] = i; pStoneArray[0] <= m/n; pStoneArray[0]++)
　　　　　　　　SplitStones(m-pStoneArray[0],n-1,pStoneArray+1);
　　　　return;
}

bool checkArray(const int &m, const int &n, const int *pStoneArray)
//检查数组中的数据是否能够拼出1~m
{
　　　　stack <int> newValue;
　　　　int i,j,k;

　　　　for(i=1;i<=m;i++)
　　　　{
　　　　　　　　value[i] = false;
　　　　}
　　　　value[pStoneArray[0]]=true;

　　　　for(i=1;i<n;i++)
　　　　{
　　　　　　　　newValue.push(pStoneArray[i]);
　　　　　　　　for(j=1;j<=m;j++)
　　　　　　　　{
　　　　　　　　　　　　if(value[j])
　　　　　　　　　　　　{
　　　　　　　　　　　　　　　　k = j+ pStoneArray[i];
　　　　　　　　　　　　　　　　if(k<=m && !value[k]) newValue.push(k);
　　　　　　　　　　　　　　　　k = j-pStoneArray[i];
　　　　　　　　　　　　　　　　if(k<0) k = -k;
　　　　　　　　　　　　　　　　if(!value[k] && k!=0) newValue.push(k);
　　　　　　　　　　　　}
　　　　　　　　}
　　　　　　　　while(!newValue.empty())
　　　　　　　　{
　　　　　　　　　　　　value[newValue.top()]=true;
　　　　　　　　　　　　newValue.pop();
　　　　　　　　}
　　　　}

　　　　for(i=1;i<=m;i++)
　　　　{
　　　　　　　　if(!value[i])break;
　　　　}
　　　　return(i==m+1);
}
//根据m,n的不同，可能无解，可能多解。比如m=5,n=2,无解。m=5,n=3,两解{1,1,3},{1,2,2}

#9

n块石头称重的最大重量为：S(n)=(3^n-1)/2
第n块石头的重量为：M(n)=3^(n-1)
归纳证明如下：
1)当n=1，时，S(1)=1,M(1)=1,公式成立。
2)假设当n为某一个正整数时,M(1),M(2),...M(n)共n块石头能称出 [1,S(n)]的不同重量。
则在加一个石头M(n+1)时，显然也可以称出[1,S(n)]　（区间１）的重量。同时也可以称出 [M(n+1)-s(n),M(n+1)-1]　（区间２），M(n+1)　（区间３），[M(n+1) +1,M(n+1)+S(n)]　（区间４）的重量。而M(n+1)+S(n)正好等于S(n+1)
下面只要再证明以上几个区间是连在一起的就可以了。
M(n+1)-S(n) = 3^n - (3^n-1)/2 = (3^n+1)/2 = S(n)+1;====>区间１和区间２是连在一起的。
很显然区间２，区间３，区间４是连在一起的。
因此 M(1),M(2),...M(n+1)所表示的重量为[1,S(n+1)]
3)哈哈，证明完成。

#10

我在代码中用了全角空格，不好意思了。