新书推介:《语义网技术体系》
作者:瞿裕忠,胡伟,程龚
   XML论坛     W3CHINA.ORG讨论区     计算机科学论坛     SOAChina论坛     Blog     开放翻译计划     新浪微博  
 
  • 首页
  • 登录
  • 注册
  • 软件下载
  • 资料下载
  • 核心成员
  • 帮助
  •   Add to Google

    >> 本版讨论高级C/C++编程、代码重构(Refactoring)、极限编程(XP)、泛型编程等话题
    [返回] 计算机科学论坛计算机技术与应用『 C/C++编程思想 』 → 一个有趣的编程题目,1,2,5这三个数不同个数组合的和为1000的组合个数 查看新帖用户列表

      发表一个新主题  发表一个新投票  回复主题  (订阅本版) 您是本帖的第 21029 个阅读者浏览上一篇主题  刷新本主题   树形显示贴子 浏览下一篇主题
     * 贴子主题: 一个有趣的编程题目,1,2,5这三个数不同个数组合的和为1000的组合个数 举报  打印  推荐  IE收藏夹 
       本主题类别:     
     pennyliang 帅哥哟,离线,有人找我吗?白羊座1979-4-7
      
      
      威望:8
      等级:大二期末(C++考了100分!)
      文章:266
      积分:1911
      门派:Lilybbs.net
      注册:2005/3/11

    姓名:(无权查看)
    城市:(无权查看)
    院校:(无权查看)
    给pennyliang发送一个短消息 把pennyliang加入好友 查看pennyliang的个人资料 搜索pennyliang在『 C/C++编程思想 』的所有贴子 引用回复这个贴子 回复这个贴子 查看pennyliang的博客楼主
    发贴心情 一个有趣的编程题目,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)
      




    点击查看用户来源及管理<br>发贴IP:*.*.*.* 2006/1/17 14:10:00
     
     pennyliang 帅哥哟,离线,有人找我吗?白羊座1979-4-7
      
      
      威望:8
      等级:大二期末(C++考了100分!)
      文章:266
      积分:1911
      门派:Lilybbs.net
      注册:2005/3/11

    姓名:(无权查看)
    城市:(无权查看)
    院校:(无权查看)
    给pennyliang发送一个短消息 把pennyliang加入好友 查看pennyliang的个人资料 搜索pennyliang在『 C/C++编程思想 』的所有贴子 引用回复这个贴子 回复这个贴子 查看pennyliang的博客2
    发贴心情 

    应该是(floor((5*i)/2)+1)[i从0,到20],特此更正
    点击查看用户来源及管理<br>发贴IP:*.*.*.* 2006/1/20 13:22:00
     
     qzlzj 帅哥哟,离线,有人找我吗?
      
      
      等级:大一新生
      文章:6
      积分:82
      门派:XML.ORG.CN
      注册:2006/1/27

    姓名:(无权查看)
    城市:(无权查看)
    院校:(无权查看)
    给qzlzj发送一个短消息 把qzlzj加入好友 查看qzlzj的个人资料 搜索qzlzj在『 C/C++编程思想 』的所有贴子 引用回复这个贴子 回复这个贴子 查看qzlzj的博客3
    发贴心情 
    学习 中...........
    点击查看用户来源及管理<br>发贴IP:*.*.*.* 2006/2/7 21:16:00
     
     bettyliu 美女呀,离线,快来找我吧!
      
      
      等级:大一新生
      文章:4
      积分:70
      门派:XML.ORG.CN
      注册:2006/3/26

    姓名:(无权查看)
    城市:(无权查看)
    院校:(无权查看)
    给bettyliu发送一个短消息 把bettyliu加入好友 查看bettyliu的个人资料 搜索bettyliu在『 C/C++编程思想 』的所有贴子 引用回复这个贴子 回复这个贴子 查看bettyliu的博客4
    发贴心情 
    嗯,不错,偏函数思想蛮不错的·~有兴趣可以去看看跳蚤程序玩玩~~有点类似的数学题~~
    点击查看用户来源及管理<br>发贴IP:*.*.*.* 2006/3/26 11:12:00
     
     firstway 帅哥哟,离线,有人找我吗?
      
      
      威望:5
      等级:大三暑假(2个月背完了红宝书)(版主)
      文章:92
      积分:947
      门派:Lilybbs.net
      注册:2005/10/31

    姓名:(无权查看)
    城市:(无权查看)
    院校:(无权查看)
    给firstway发送一个短消息 把firstway加入好友 查看firstway的个人资料 搜索firstway在『 C/C++编程思想 』的所有贴子 引用回复这个贴子 回复这个贴子 查看firstway的博客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"

    点击查看用户来源及管理<br>发贴IP:*.*.*.* 2006/3/26 13:03:00
     
     firstway 帅哥哟,离线,有人找我吗?
      
      
      威望:5
      等级:大三暑假(2个月背完了红宝书)(版主)
      文章:92
      积分:947
      门派:Lilybbs.net
      注册:2005/10/31

    姓名:(无权查看)
    城市:(无权查看)
    院校:(无权查看)
    给firstway发送一个短消息 把firstway加入好友 查看firstway的个人资料 搜索firstway在『 C/C++编程思想 』的所有贴子 引用回复这个贴子 回复这个贴子 查看firstway的博客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()

    点击查看用户来源及管理<br>发贴IP:*.*.*.* 2006/3/26 13:04:00
     
     firstway 帅哥哟,离线,有人找我吗?
      
      
      威望:5
      等级:大三暑假(2个月背完了红宝书)(版主)
      文章:92
      积分:947
      门派:Lilybbs.net
      注册:2005/10/31

    姓名:(无权查看)
    城市:(无权查看)
    院校:(无权查看)
    给firstway发送一个短消息 把firstway加入好友 查看firstway的个人资料 搜索firstway在『 C/C++编程思想 』的所有贴子 引用回复这个贴子 回复这个贴子 查看firstway的博客7
    发贴心情 
    结果应该有541条
    right?
    点击查看用户来源及管理<br>发贴IP:*.*.*.* 2006/3/26 13:19:00
     
     elfstone 帅哥哟,离线,有人找我吗?射手座1983-12-6
      
      
      等级:大四(总算啃完XML规范了)
      文章:185
      积分:1177
      门派:IEEE.ORG.CN
      注册:2006/2/25

    姓名:(无权查看)
    城市:(无权查看)
    院校:(无权查看)
    给elfstone发送一个短消息 把elfstone加入好友 查看elfstone的个人资料 搜索elfstone在『 C/C++编程思想 』的所有贴子 引用回复这个贴子 回复这个贴子 查看elfstone的博客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...

    点击查看用户来源及管理<br>发贴IP:*.*.*.* 2006/3/26 23:37:00
     
     elfstone 帅哥哟,离线,有人找我吗?射手座1983-12-6
      
      
      等级:大四(总算啃完XML规范了)
      文章:185
      积分:1177
      门派:IEEE.ORG.CN
      注册:2006/2/25

    姓名:(无权查看)
    城市:(无权查看)
    院校:(无权查看)
    给elfstone发送一个短消息 把elfstone加入好友 查看elfstone的个人资料 搜索elfstone在『 C/C++编程思想 』的所有贴子 引用回复这个贴子 回复这个贴子 查看elfstone的博客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...

    点击查看用户来源及管理<br>发贴IP:*.*.*.* 2006/3/26 23:42:00
     
     firstway 帅哥哟,离线,有人找我吗?
      
      
      威望:5
      等级:大三暑假(2个月背完了红宝书)(版主)
      文章:92
      积分:947
      门派:Lilybbs.net
      注册:2005/10/31

    姓名:(无权查看)
    城市:(无权查看)
    院校:(无权查看)
    给firstway发送一个短消息 把firstway加入好友 查看firstway的个人资料 搜索firstway在『 C/C++编程思想 』的所有贴子 引用回复这个贴子 回复这个贴子 查看firstway的博客10
    发贴心情 

    是可以写的简单些
    点击查看用户来源及管理<br>发贴IP:*.*.*.* 2006/3/28 15:05:00
     
     GoogleAdSense
      
      
      等级:大一新生
      文章:1
      积分:50
      门派:无门无派
      院校:未填写
      注册:2007-01-01
    给Google AdSense发送一个短消息 把Google AdSense加入好友 查看Google AdSense的个人资料 搜索Google AdSense在『 C/C++编程思想 』的所有贴子 访问Google AdSense的主页 引用回复这个贴子 回复这个贴子 查看Google AdSense的博客广告
    2024/11/25 16:39:25

    本主题贴数14,分页: [1] [2]

    管理选项修改tag | 锁定 | 解锁 | 提升 | 删除 | 移动 | 固顶 | 总固顶 | 奖励 | 惩罚 | 发布公告
    W3C Contributing Supporter! W 3 C h i n a ( since 2003 ) 旗 下 站 点
    苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
    78.125ms