中文XML论坛--一个有趣的编程题目，1，2，5这三个数不同个数组合的和为1000的组合个数

新书推介：《语义网技术体系》
作者：瞿裕忠，胡伟，程龚

XML论坛

W3CHINA.ORG讨论区

计算机科学论坛

SOAChina论坛

Blog

开放翻译计划

新浪微博

首页

软件下载

资料下载

核心成员

帮助

>> 本版讨论高级C/C++编程、代码重构(Refactoring)、极限编程(XP)、泛型编程等话题

[返回] 中文XML论坛 - 专业的XML技术讨论区 → 计算机技术与应用 → 『 C/C++编程思想』 → 一个有趣的编程题目，1，2，5这三个数不同个数组合的和为1000的组合个数

◇查看新帖 ◇ 用户列表 ◇

(订阅本版)

您是本帖的第 20662 个阅读者　　

*	贴子主题：一个有趣的编程题目，1，2，5这三个数不同个数组合的和为1000的组合个数	举报打印推荐 IE收藏夹
	本主题类别:

pennyliang

  威望：8
  等级：大二期末(C++考了100分!)
  文章：266
  积分：1911
  门派：Lilybbs.net
  注册：2005/3/11

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	楼主

一个有趣的编程题目，1，2，5这三个数不同个数组合的和为1000的组合个数

程序要求功能：求出用1，2，5这三个数不同个数组合的和为100的组合个数。如：100个1是一个组合，5个1加19个5是一个组合。。。。
　　请用C++语言写。
我的解法
定义三元组集合(x,y,z)上的偏函数,其中x,y,z都是正整数，满足(1,2,5)*(x,y,z)T=100, (x,y,z)T表示(x,y,z)转置。x+2y+5z=100。
　　
　　那么求该偏函数对应的集合的基数即是本题答案
　　
　　可知z最大取20，那么来看规律
　　可能的答案为
　　(0,0，20)
　　(1，2，19)
　　(3，1，19)
      (5，0，19)
　　....
　　不难分析,答案为 1+ 求和（floor((5*i)/2)+1）[i从1，到20]，
　　算法复杂度为O(n),

原文连接
http://www5.tianya.cn/new/techforum/Content.asp?idWriter=2563455&Key=817608499&idItem=414&idArticle=1035

[此贴子已经被作者于2006-1-17 17:24:15编辑过]

   收藏   分享
顶(0)

2006/1/17 14:10:00

pennyliang

  威望：8
  等级：大二期末(C++考了100分!)
  文章：266
  积分：1911
  门派：Lilybbs.net
  注册：2005/3/11

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第2楼

应该是（floor((5*i)/2)+1）[i从0，到20]，特此更正

2006/1/20 13:22:00

qzlzj

  等级：大一新生
  文章：6
  积分：82
  门派：XML.ORG.CN
  注册：2006/1/27

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第3楼

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

2006/2/7 21:16:00

bettyliu

  等级：大一新生
  文章：4
  积分：70
  门派：XML.ORG.CN
  注册：2006/3/26

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第4楼

嗯，不错，偏函数思想蛮不错的·～有兴趣可以去看看跳蚤程序玩玩～～有点类似的数学题～～

2006/3/26 11:12:00

firstway

  威望：5
  等级：大三暑假(2个月背完了红宝书)(版主)
  文章：92
  积分：947
  门派：Lilybbs.net
  注册：2005/10/31

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第5楼

试着给出c代码(1)

//this is "sum100.h" writen by firstway
#include "stdio.h"
#define SUM_NUM 100
extern int NUMS[];

int do_1(int xyz[]);
int do_2(int xyz[]);
int do_3(int xyz[]);
int sum_into(int xyz[])
{
if(xyz[0]<0)//未处理20的系数
{
  do_1(xyz);
}
else if(xyz[1]<0)
{
  do_2(xyz);
}
else if(xyz[2]<0)
{
  do_3(xyz);
}
return 0;
}
int do_1(int xyz[])
{
int cur_sum;
int times;
int i;

cur_sum=SUM_NUM;
times=cur_sum/NUMS[0];

for(i=0;i<=times;i++)
{
  xyz[0]=i;
  xyz[1]=-1;
  xyz[2]=-1;
  sum_into( xyz );
}
return 0;
}
int do_2(int xyz[])
{
int cur_sum;
int times;
int i;

cur_sum=SUM_NUM-xyz[0]*NUMS[0];
times=cur_sum/NUMS[1];

for(i=0;i<=times;i++)
{
  xyz[1]=i;
  xyz[2]=-1;
  sum_into( xyz );
}

return 0;
}
int do_3(int xyz[])
{
int cur_sum=SUM_NUM-xyz[0]*NUMS[0]-xyz[1]*NUMS[1];
xyz[2]=cur_sum/NUMS[2];

printf("(%2d, %2d, %2d)\n",xyz[0],xyz[1],xyz[2]);
return 0;
}
// end of "sum100.h"

2006/3/26 13:03:00

firstway

  威望：5
  等级：大三暑假(2个月背完了红宝书)(版主)
  文章：92
  积分：947
  门派：Lilybbs.net
  注册：2005/10/31

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第6楼

试着给出c代码(2)
//this is main()
#include "stdio.h"
#include "sum100.h"

int NUMS[]={5,2,1};
int main()
{
int xyz[3]={-1,-1,-1};

sum_into( xyz );

return 0;

}
//end of main()

2006/3/26 13:04:00

firstway

  威望：5
  等级：大三暑假(2个月背完了红宝书)(版主)
  文章：92
  积分：947
  门派：Lilybbs.net
  注册：2005/10/31

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第7楼

结果应该有541条
right？

2006/3/26 13:19:00

elfstone

  等级：大四(总算啃完XML规范了)
  文章：185
  积分：1177
  门派：IEEE.ORG.CN
  注册：2006/2/25

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第8楼

541是对的。。。
我写的算法，大家看一下。。。
#include "iostream"
using namespace std;
int main()
{
    int i,j,x,n=0;
    for(i=0;i<=20;i++)
    {
        x=100-i*5;
        for(j=0;j<=x/2;j++)
        {
            ++n;
            cout<<i<<' '<<j<<' '<<x-2*j<<endl;
        }
    }
    cout<<"Total is:"<<n<<endl;
    system("PAUSE");
}

[此贴子已经被作者于2006-3-27 8:28:23编辑过]
----------------------------------------------
Ich liebe erst meines Leben...

2006/3/26 23:37:00

elfstone

  等级：大四(总算啃完XML规范了)
  文章：185
  积分：1177
  门派：IEEE.ORG.CN
  注册：2006/2/25

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第9楼

firstway可能是受到楼主有关于偏函数说法的影响了，其实没必要用偏函数的。。。
题目要求的条件是 i+2*j+5*k==100 （i,j,k分别是1,2,5的个数）
稍变化一下就行了i==100-2*j-5*k（这样就可以减少不必要的运算，减少运算时间。。。）这就是我的算法思想。。。

[此贴子已经被作者于2006-3-27 8:25:12编辑过]
----------------------------------------------
Ich liebe erst meines Leben...

2006/3/26 23:42:00

firstway

  威望：5
  等级：大三暑假(2个月背完了红宝书)(版主)
  文章：92
  积分：947
  门派：Lilybbs.net
  注册：2005/10/31

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第10楼

恩
是可以写的简单些

2006/3/28 15:05:00

GoogleAdSense

  等级：大一新生
  文章：1
  积分：50
  门派：无门无派
  院校：未填写
  注册：2007-01-01

	广告

2024/5/1 18:09:45

本主题贴数14，分页： [1] [2]

管理选项：修改tag | 锁定 | 解锁 | 提升 | 删除 | 移动 | 固顶 | 总固顶 | 奖励 | 惩罚 | 发布公告


	W 3 C h i n a ( since 2003 ) 旗下站点苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	171.875ms