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

    >> We choose to study algorithmic problems,  not because they are easy,  but because they are hard.
    [返回] 中文XML论坛 - 专业的XML技术讨论区 → 计算机理论与工程 → 『 算法理论与分析 』 → 一个很难的数学算法大家进来帮帮小妹啊很急 ◇查看新帖 ◇ 用户列表 ◇

      发表一个新主题  发表一个新投票  回复主题  (订阅本版) 您是本帖的第 77109 个阅读者浏览上一篇主题  刷新本主题   树形显示贴子　浏览下一篇主题
     * 贴子主题： 一个很难的数学算法大家进来帮帮小妹啊很急 举报  打印  推荐  IE收藏夹 
       本主题类别:     
     dhxu757 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：2
      积分：68
      门派：XML.ORG.CN
      注册：2006/4/18

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给dhxu757发送一个短消息 把dhxu757加入好友 查看dhxu757的个人资料 搜索dhxu757在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看dhxu757的博客第21楼
    发贴心情 

    一个很简单的问题, 可以不要涉及到高深的算法即可求解.我的程序在楼上.请大家指正.
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/4/18 22:03:00
     
     yibical 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：2
      积分：77
      门派：XML.ORG.CN
      注册：2006/4/29

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给yibical发送一个短消息 把yibical加入好友 查看yibical的个人资料 搜索yibical在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看yibical的博客第22楼
    发贴心情 
    算法我想出来了，可以和我联系QQ:401350842
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/4/29 10:44:00
     
     tomlillite 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：1
      积分：60
      门派：XML.ORG.CN
      注册：2006/5/6

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给tomlillite发送一个短消息 把tomlillite加入好友 查看tomlillite的个人资料 搜索tomlillite在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看tomlillite的博客第23楼
    发贴心情 
    #include<iostream.h>
    void main()
    {int n;
    cout<<"请输入要分解的数据："<<endl;
    cin>>n;
    int a,b,c,d;
    for(a=1;a<n;a++)
    {for(b=a;b<n;b++)
    {for(c=b;c<n;c++)
    {for(d=c;d<n;d++)
       {if(a+b+c+d==n&&a<=b&&b<=c&&c<=d)
           cout<<a<<" "<<b<<" "<<c<<" "<<d<<endl;
       }
    }
    }
    }
    }
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/5/9 10:56:00
     
     wanghuicn2008 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：1
      积分：59
      门派：XML.ORG.CN
      注册：2006/6/24

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给wanghuicn2008发送一个短消息 把wanghuicn2008加入好友 查看wanghuicn2008的个人资料 搜索wanghuicn2008在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看wanghuicn2008的博客第24楼
    发贴心情 
    组合数学中的母函数可解这个问题，具体看《组合数学及算法》中科大出的
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/7/1 16:58:00
     
     binaryluo 帅哥哟，离线，有人找我吗？
      
      
      威望：6
      等级：研二(Pi-Calculus看得一头雾水)(版主)
      文章：679
      积分：5543
      门派：IEEE.ORG.CN
      注册：2005/2/19

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给binaryluo发送一个短消息 把binaryluo加入好友 查看binaryluo的个人资料 搜索binaryluo在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看binaryluo的博客第25楼
    发贴心情 
    看了大家写的程序实现，作了个总结。

    解决方法大致可以分为以下两种思路：
    1.简单的循环测试。这种方法的时间复杂度是O(m^n)，注：m^n表示m的n次方。这种方法的代表是：14楼，15楼，23楼。其中，15楼采用递归实现，但在时间复杂度上跟用非递归实现是一样的。

    2.将结果的数串以一个整体（大整数）考虑，先设置好循环的范围，然后再在该范围内测试这些大整数的各个数位取出来相加，看结果是否是正确解。例如m=8,n=4，意思是找出4个数字相加的结果是8的全部组合。用方法2的思想，他的处理思路是，4个数字如果组成一个大整数的话，范围是1000-9999之间，即10^3到10^4之间，所以原题可以考虑成在1000-9999之间找出各个数位加起来是8的全部数字。取各个数位的时候采用了模10的方法。
    这种方法只有一个循环，但是该循环的范围比较大，而且中间在取各个数位的时候也有一个常数阶的循环，这种方法的时间复杂可表示为O(n*(10^n - 10^(n-1)))。这种方法的代表是：17楼，20楼。前者是java版的，后者是C语言版的。

    可以证明两算法的时间复杂度满足如下关系：
    当m<=10时，m^n < n*(10^n - 10^(n-1))；
    当m > 10时，m^n > n*(10^n - 10^(n-1))。

    在分析过程中略去了有些朋友的解法，在此表示歉意。另外，由于个人水品有限，在分析过程中如果有错误的地方还望大家指正。

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/7/2 11:23:00
     
     richardxx 帅哥哟，离线，有人找我吗？双鱼座1987-2-24
      
      
      等级：大一新生
      文章：4
      积分：76
      门派：IEEE.ORG.CN
      注册：2006/8/22

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给richardxx发送一个短消息 把richardxx加入好友 查看richardxx的个人资料 搜索richardxx在『 算法理论与分析 』的所有贴子 点击这里发送电邮给richardxx 引用回复这个贴子 回复这个贴子 查看richardxx的博客第26楼
    发贴心情 
    #include <stdio.h>

    int f(int m,int n)
    {
     int i;
     int s=0;
     int stop;
     if (m==n)
      return 1;
     stop=m-n>n?n:m-n;
     for (i=1;i<=stop;++i)
      s+=f(m-n,i);
     return s;
    }

    int main()
    {
     int m,n,result;
     scanf("%d %d",&m,&n);
     result=f(m,n);
     printf("\nThe answer is:%d\n",result);
     return 0;
    }

    ----------------------------------------------
    出国真的那么遥远么？

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/8/24 11:11:00
     
     richardxx 帅哥哟，离线，有人找我吗？双鱼座1987-2-24
      
      
      等级：大一新生
      文章：4
      积分：76
      门派：IEEE.ORG.CN
      注册：2006/8/22

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给richardxx发送一个短消息 把richardxx加入好友 查看richardxx的个人资料 搜索richardxx在『 算法理论与分析 』的所有贴子 点击这里发送电邮给richardxx 引用回复这个贴子 回复这个贴子 查看richardxx的博客第27楼
    发贴心情 
    以上的程序直接利用关系式:

    f(m,n)=sum{[i=1 to min(m-n,n)] f(m-n,i)}
    这种题数学方法是最简单的。

    ----------------------------------------------
    出国真的那么遥远么？

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/8/24 11:15:00
     
     dvdface 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：8
      积分：89
      门派：XML.ORG.CN
      注册：2008/1/23

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给dvdface发送一个短消息 把dvdface加入好友 查看dvdface的个人资料 搜索dvdface在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看dvdface的博客第28楼
    发贴心情 
    这不就是枚举么? 为什么难啊?

    还可以用减枝法来减少计算量.

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2008/10/24 17:16:00
     
     richardxx 帅哥哟，离线，有人找我吗？双鱼座1987-2-24
      
      
      等级：大一新生
      文章：4
      积分：76
      门派：IEEE.ORG.CN
      注册：2006/8/22

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给richardxx发送一个短消息 把richardxx加入好友 查看richardxx的个人资料 搜索richardxx在『 算法理论与分析 』的所有贴子 点击这里发送电邮给richardxx 引用回复这个贴子 回复这个贴子 查看richardxx的博客第29楼
    发贴心情 
    以下是引用dvdface在2008-10-24 17:16:00的发言：
    这不就是枚举么? 为什么难啊?

    还可以用减枝法来减少计算量.


    汗，枚举，人家要的是DP解。。。

    ----------------------------------------------
    出国真的那么遥远么？

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2008/10/24 17:22:00
     
     dvdface 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：8
      积分：89
      门派：XML.ORG.CN
      注册：2008/1/23

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给dvdface发送一个短消息 把dvdface加入好友 查看dvdface的个人资料 搜索dvdface在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看dvdface的博客第30楼
    发贴心情 
    有道理, 用DP可以更加减少计算量. 就是实现麻烦点.

    要存储 子问题的 解.

    不错

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2008/10/24 18:42:00
     
     GoogleAdSense
      
      
      等级：大一新生
      文章：1
      积分：50
      门派：无门无派
      院校：未填写
      注册：2007-01-01
    给Google AdSense发送一个短消息 把Google AdSense加入好友 查看Google AdSense的个人资料 搜索Google AdSense在『 算法理论与分析 』的所有贴子 访问Google AdSense的主页 引用回复这个贴子 回复这个贴子 查看Google AdSense的博客广告
    2025/9/26 12:55:19

    本主题贴数39，分页： [1] [2] [3] [4]

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