一个关于从1到100的加法算法

sum = 5050;速度超级块!!!!!

设X，100=X+1；X=X+1；
当X=2时，1+1=2，就1种
当X=3时，1+1+1=1+2=3，就2种

以此类推，当X=99时，有98种
也就是1到98连续相加

to:hy_lihuan
写出循环代码

楼上许过仁兄都没有看清楼主的题意。
这是典型的类似背包问题的算法，中级程序员必掌握的算法。
这个算法简单的解决就用穷举法，算法可用递归和堆栈均可，我个人喜欢用堆栈，下面是我以前用PB编的堆栈算法。由于用了一些函数和实例变量，就没有一一帖出，只是部分代码。
实现了从n个物品中任意选出m个组合的程序（m<=n）
do while true
temp++
if temp>10000 then
messagebox('警告！ii_num='+string(ii_num),'可能是死循环哟！再来再来...')
exit
end if
wf_input(id)
lb_weight=wf_weight()
if lb_weight=true then//重量未超限，继续移入下一个物品
if stack[1]=ii_num then
wf_output()//找到最后符合重量的一种组合
exit
end if
if id=ii_num then
wf_output()
wf_pop()
wf_pop()
id=wf_gettop()+1
else
id=wf_gettop()+1
end if
end if
if lb_weight=false then//重量超限,移出超重的物品，继续移入下一个物品
if stack[1]=ii_num then
exit
end if
if id=ii_num then
wf_pop()
if stack[1]>0 then
wf_output()//找到符合重量的一种组合
id=wf_gettop()+1
wf_pop()
wf_pop()
end if
else
id=wf_gettop()+1
wf_pop()
end if
end if
loop

这种问题没有高效的,我遇到过和这个问题差多不的一个问题,当然是"实际化"了的,有N种商品,单价不定,存货数量无限,客户支付了一个定额金额,还原出用户购买商品的数量和种类,要求只得出一个结果就可以.当然的我需求可不是纸上谈兵,是实际需要,我思索了这个问题近五年,也没得出一个快速的解法,而且我这个问题解决方案的语言不限,LZ的这个问题,和我的这个问题差不多,只能说解法有,最高效的算法,不可能有.

这种问题没有高效的,我遇到过和这个问题差多不的一个问题,当然是"实际化"了的,有N种商品,单价不定,存货数量无限,客户支付了一个定额金额,还原出用户购买商品的数量和种类,要求只得出一个结果就可以.当然的我需求可不是纸上谈兵,是实际需要,我思索了这个问题近五年,也没得出一个快速的解法,而且我这个问题解决方案的语言不限,LZ的这个问题,和我的这个问题差不多,只能说解法有,最高效的算法,不可能有.
__________________________________________________________________________________
同意你的说法，不过你想了五年，不至于吧。真的有这么复杂吗？

用C＋＋写的，效率不高：#include <iostream>
#include <vector>
#define N 100
using namespace std;int check(vector<int>& ivec)
{
    int sum=0;
    for (vector<int>::iterator it=ivec.begin(); it!=ivec.end(); it++)
        sum += *it;
    if (sum==N) return 0;
    else if (sum<N) return 1;
    else return 2;
}void Backtrack(vector<int>& ivec, int i)
{
    int flag=check(ivec);
    if (flag==2) return;
    if (i==N+1)
    {
        if (flag==0)
        {
            for (vector<int>::iterator it=ivec.begin(); it!=ivec.end(); it++)
                cout<<*it<<' ';
            cout<<endl;
        }
    }
    else
    {
        ivec.push_back(i);
        Backtrack(ivec, i+1);
        ivec.pop_back();
        Backtrack(ivec, i+1);
    }
}int main()
{
    vector<int> ivec;
    Backtrack(ivec,1);    system("pause");
}

穷举就是了，简单插播一条广告，小店新开张，优惠出售各种手工艺品，欢迎大家选购，是各位帅哥送女朋友、老婆、情人(OR各位美女送男朋友、老公、情人)的不二选择
http://shop33881320.taobao.com/

c#的，随便写写的，不要挑剔编码不规范啊
基本思路是，等式中的数字都按从小到大的顺序寻找，比如1+2+3。
如果已经决定等式包括1+2，那么下一个数字在从3到97之间，而剩下部分的总和是97
如果总和大于下一个数字，那么将总和减去下一个数字，继续寻找剩下的部分，比如第3个数字是3，那么新的总和就是97-3=94，再下一个数字在4到94之间
如果总和等与下一个数字，那么等式完成，比如第3个数字是97，1+2+97
如果总和小于下一个数字，那么等式不成立，放弃比如 1+2+90+7，而1+2+7+90在之前已经出现过了，重复，所以要放弃
代码如下       int euqCount = 0;       void do()
       {
   /用StringCollection保存所有等式
            StringCollection equs=new StringCollection();            /等式中最小的数从1到49
            for (int i=1;i<50;i++)
            {
                getEqu(equs,i,100,"");
            }
        }

        /init 等式中下一个数
        /sum 100减去当前等式中已有数字的和所剩之余数
        /curEqu 当前等式已决定的部分

        void getEqu(StringCollection equs, int init, int sum, string curEqu)
        {
            string cEuq;
            if (sum==init) /如果余数与下一个数相等，则当前等式计算完毕
            {
                equs.Add(curEqu + '+' + init.ToString());
                euqCount++;
                return;
            }
            else   /如果余数大于下一个数，则将余数减去下一个数，寻找等式剩余部分
            {
                int remain=sum-init;
                for (int i=init+1;i<=remain;i++)
                {
                    if (curEqu == "") cEuq = init.ToString();
                    else cEuq = curEqu + '+' + init.ToString();
                    getEqu(equs, i, remain, cEuq);
                }
            }
        }一共有444792种组合

答案：所有算法共计：444792
代码如下：
//其实只需要调用allArraySum方法即可得到答案，速度很快
//printAddArray是为了列举出所有算法组合,速度较慢//总计所有算法
private void allArraySum(ref long sum,int start,int end)
{
int tempEnd;
int _end; if((end % 2)==0)
_end=end/2-1;
else
_end=end/2; sum=sum+_end-start; for(int i=start+1;i<=_end;i++)
{
tempEnd= end - i; if((tempEnd-i-1)>i)
{
allArraySum(ref sum, i, tempEnd);
}
}}//列举出所有的算法组合以及总计所有算法
private void printAddArray(ref long sum,string lastArray,int start,int end)
{
string tempArray;
int tempEnd;
int _end; if((end % 2)==0)
_end=end/2-1;
else
_end=end/2; for(int i=start+1;i<=_end;i++)
{
tempEnd= end - i;
System.Console.WriteLine(lastArray + i + "+" + tempEnd);
sum++;
if((tempEnd-i-1)>i)
{
tempArray = lastArray + i + "+";
printAddArray(ref sum,tempArray, i, tempEnd);
}
}
}//测试以上算法
private void button1_Click(object sender, System.EventArgs e)
{
long _sum=0;
printAddArray(ref _sum,"",0,100);
System.Console.WriteLine("全部的组合共计："+_sum);
}private void button2_Click(object sender, System.EventArgs e)
{
long _sum=0;
allArraySum(ref _sum,0,100);
System.Console.WriteLine("全部的组合共计："+_sum);
MessageBox.Show(_sum.ToString());

}button2_Click运行结果：
全部的组合共计：444792
button1_Click运行结果：
1+99
1+2+97
1+2+3+94
1+2+3+4+90
1+2+3+4+5+85
1+2+3+4+5+6+79
1+2+3+4+5+6+7+72
1+2+3+4+5+6+7+8+64
1+2+3+4+5+6+7+8+9+55
1+2+3+4+5+6+7+8+9+10+45
1+2+3+4+5+6+7+8+9+10+11+34
1+2+3+4+5+6+7+8+9+10+11+12+22
1+2+3+4+5+6+7+8+9+10+11+13+21
1+2+3+4+5+6+7+8+9+10+11+14+20
1+2+3+4+5+6+7+8+9+10+11+15+19
1+2+3+4+5+6+7+8+9+10+11+16+18
1+2+3+4+5+6+7+8+9+10+12+33
1+2+3+4+5+6+7+8+9+10+12+13+20
1+2+3+4+5+6+7+8+9+10+12+14+19
1+2+3+4+5+6+7+8+9+10+12+15+18
1+2+3+4+5+6+7+8+9+10+12+16+17
1+2+3+4+5+6+7+8+9+10+13+32
1+2+3+4+5+6+7+8+9+10+13+14+18
1+2+3+4+5+6+7+8+9+10+13+15+17
1+2+3+4+5+6+7+8+9+10+14+31
1+2+3+4+5+6+7+8+9+10+14+15+16
1+2+3+4+5+6+7+8+9+10+15+30
1+2+3+4+5+6+7+8+9+10+16+29
1+2+3+4+5+6+7+8+9+10+17+28
1+2+3+4+5+6+7+8+9+10+18+27
1+2+3+4+5+6+7+8+9+10+19+26
1+2+3+4+5+6+7+8+9+10+20+25
1+2+3+4+5+6+7+8+9+10+21+24
1+2+3+4+5+6+7+8+9+10+22+23
1+2+3+4+5+6+7+8+9+11+44
1+2+3+4+5+6+7+8+9+11+12+32
1+2+3+4+5+6+7+8+9+11+12+13+19
1+2+3+4+5+6+7+8+9+11+12+14+18
。。
29+31+40
29+32+39
29+33+38
29+34+37
29+35+36
30+70
30+31+39
30+32+38
30+33+37
30+34+36
31+69
31+32+37
31+33+36
31+34+35
32+68
32+33+35
33+67
34+66
35+65
36+64
37+63
38+62
39+61
40+60
41+59
42+58
43+57
44+56
45+55
46+54
47+53
48+52
49+51
全部的组合共计：444792

有兴趣的朋友可以把参数改小点测试：
如列举出和为10的所有算法：
long _sum=0;
printAddArray(ref _sum,"",0,10);
System.Console.WriteLine("全部的组合共计："+_sum);
总计和为10的所有算法：
long _sum=0;
allArraySum(ref _sum,0,10);
System.Console.WriteLine("全部的组合共计："+_sum);
MessageBox.Show(_sum.ToString());

好像只有“solsolsol(秋水萧萧)”的想法是对的吧，用试探回溯的方法可以解出：初始化：int work[100] = {0};
        int ptr = 0;试探过程：当前指针位置的数减一，加到后面,指针右移一位,如果当前位置的数比前面的大，继
          续试探，否则生成了一个新的组合，这时若当前的数大于1，继续试探生成新的组
          合，否则转到回溯过程；回溯过程：(1)如果当前指针前面的数大于1，则指针左移一位，重新开始试探过程；
          (2)否则，当前指针位置的数加到前面，当前位置置0，返回(1)的判断。100
99 + 1
98 + 2
98 + 1 + 1
97 + 3
97 + 2 + 1
97 + 1 + 1 + 1
96 + 4
96 + 3 + 1
96 + 2 + 2
96 + 2 + 1 + 1
96 + 1 + 1 + 1 + 1
95 + 5
95 + 4 + 1
95 + 3 + 2
95 + 3 + 1 + 1
95 + 2 + 2 + 1
......

有一地方搞错了初始化： work[0] = 100;

flysky198() 的代码明显牛头不对马嘴，要求"数字不能重复"。
众多高人说n*(n-1)/2，恕我愚昧，看半天不知所云，，，愿出100分赏予利用n*(n-1)/2给出完全代码者

lw1a2(一刀 Blog：http://blog.csdn.net/lw1a2/)中讲的代码怎么不行的???

代码稍作一下优化：
//总计所有算法
private void allArraySum(ref long sum,int start,int end)
{
int tempEnd;
int _end; if((end % 2)==0)
_end=end/2-1;
else
_end=end/2; sum=sum+_end-start; for(int i=start+1;i<=_end;i++)
{
tempEnd= end - i; if(tempEnd>2*(i+1))
{
allArraySum(ref sum, i, tempEnd);
}
}}//列举出所有的算法组合以及总计所有算法
private void printAddArray(ref long sum,string lastArray,int start,int end)
{
string tempArray;
int tempEnd;
int _end; if((end % 2)==0)
_end=end/2-1;
else
_end=end/2; for(int i=start+1;i<=_end;i++)
{
tempEnd= end - i;
System.Console.WriteLine(lastArray + i + "+" + tempEnd);
sum++;
if(tempEnd>2*(i+1))
{
tempArray = lastArray + i + "+";
printAddArray(ref sum,tempArray, i, tempEnd);
}
}
}

感谢各位，特别是noahfang() ，LANXUEFEI(蓝血)
两位的思路不错，这种算法，运用很广。
希望大家都学习一下。

随手用Ｃ＃写了一下实现代码，部分结果如下：
...
1+2+3+4+5+6+7+8+9+10+14+15+16
1+2+3+4+5+6+7+8+9+11+12+13+19
1+2+3+4+5+6+7+8+9+11+12+14+18
1+2+3+4+5+6+7+8+9+11+12+15+17
1+2+3+4+5+6+7+8+9+11+13+14+17
1+2+3+4+5+6+7+8+9+11+13+15+16
1+2+3+4+5+6+7+8+9+12+13+14+16
1+2+3+4+5+6+7+8+10+11+12+13+18
1+2+3+4+5+6+7+8+10+11+12+14+17
1+2+3+4+5+6+7+8+10+11+12+15+16
1+2+3+4+5+6+7+8+10+11+13+14+16
1+2+3+4+5+6+7+8+10+12+13+14+15
1+2+3+4+5+6+7+9+10+11+12+13+17
1+2+3+4+5+6+7+9+10+11+12+14+16
1+2+3+4+5+6+7+9+10+11+13+14+15
1+2+3+4+5+6+8+9+10+11+12+13+16
1+2+3+4+5+6+8+9+10+11+12+14+15
1+2+3+4+5+7+8+9+10+11+12+13+15
1+2+3+4+6+7+8+9+10+11+12+13+14
Start Time:     2006-9-5 10:53:24
End Time:       2006-9-5 10:58:39
Total Time:     00:05:14.3906250
Total Count:    444792如果不输出式子，结果如下：
Start Time:     2006-9-5 11:01:13
End Time:       2006-9-5 11:01:14
Total Time:     00:00:01.8750000
Total Count:    444792完整代码如下：
/**////[email protected]
///2006-09-05
using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;
namespace OneToHundred
{
    class Program
    {
        static ArrayList alFormula = new ArrayList();
        static string strTempFormula;        static void Main(string[] args)
        {
            DateTime dtStart = DateTime.Now;            AddFormula("",1,100);            for (int i = 0; i < alFormula.Count; i++)
            {
                string strTemp = alFormula[i].ToString();
                string[] str = strTemp.Split("+".ToCharArray());                strTemp = strTemp.Substring(0, strTemp.Length - str[str.Length - 1].ToString().Length);                AddFormula(strTemp, int.Parse(str[str.Length - 2]) + 1, int.Parse(str[str.Length - 1]));
            }            DateTime dtEnd = DateTime.Now;            TimeSpan ts = DateTime.Now.Subtract(dtStart);
            double count= ts.TotalMilliseconds;            Console.WriteLine("Start Time:\t" + dtStart);
            Console.WriteLine("End Time:\t" + dtEnd);
            Console.WriteLine("Total Time:\t" + ts);
            Console.WriteLine("Total Count:\t" + alFormula.Count);
            Console.ReadLine();
        }        static void AddFormula(string Formual,int Start, int End)
        {
            int intTemp = (int)Math.Round((double)(End / 2));            if (End % 2 != 0)
            {
                intTemp += 1;
            }            for (int i = Start; i < intTemp; i++)
            {
                strTempFormula = Formual + i.ToString() + "+" + (End - i).ToString();
                //Console.WriteLine(strTempFormula);    //显示每个满足条件的式子
                alFormula.Add(strTempFormula);
            }
        }
    }
}

.586
.model flat,stdcall
option casemap:none include windows.inc include user32.inc
include kernel32.inc
include shell32.inc
include masm32.incincludelib user32.lib
includelib kernel32.lib
includelib shell32.lib
includelib masm32.libinclude C:\masm32\macros\MACROS.ASM.data
fmt_num db "%d",0
fmt_my db "%d+%d+%d+%d+%d+%d+%d+%d+%d+%d+%d+%d+%d",10,0
szDestClass db 'Notepad',0
fmt_result db '计算结果：共计：%d  计算耗时：%d ms',0.data?
hInstance dd ?
tmpstr db 128 dup (?).code;结果输出
_SendtoNotepad proc _lpsz
local @hWinNotepad invoke FindWindow,addr szDestClass,NULL
.if eax
mov ecx,eax
invoke ChildWindowFromPoint,ecx,20,20
.endif
.if eax
mov @hWinNotepad,eax
mov esi,_lpsz
@@:
lodsb
or al,al
jz @F
movzx eax,al
invoke PostMessage,@hWinNotepad,WM_CHAR,eax,1
jmp @B
@@:
.endif
ret_SendtoNotepad endp;eax=0 now为0;my(num[1]...num[13],j)
;{
; num[j+1]=num[j]-num[j-1];
; num[j]=num[j-1];
; for(1)
; {num[j]++;
;  num[j+1]--;
;  for(i=j;i<13;++i)
;    { my (num[1],num[2],..num[13],i);}
;  if(num[j+1]<num[j])
;    {break;}
;  cout++;
; }
;}
;my(1,99,0,0,0,0,0,2);
_cout proc @n,@n2,@n3,@n4,@n5,@n6,@n7,@n8,@n9,@n10,@n11,@n12,@n13,@i

mov ecx,@i
mov eax,@n[ecx]
mov edx,@n[ecx-4]
sub eax,edx

@@: inc edx
dec eax
.if eax <= edx
xor eax,eax
ret
.endif
mov @n[ecx+4],eax
mov @n[ecx],edx
inc edi
;如果需要结果输出的话，下面一段可用，但时间上很慢好像。
; push eax
; pushad
; invoke wsprintf,addr tmpstr,addr fmt_my,@n,@n2,@n3,@n4,@n5,@n6,@n7,@n8,@n9,@n10,@n11,@n12,@n13
; invoke _SendtoNotepad,addr tmpstr
; popad
; pop eax .if ecx < 2ch
add ecx,4
invoke _cout,@n,@n2,@n3,@n4,@n5,@n6,@n7,@n8,@n9,@n10,@n11,@n12,@n13,ecx
.endif
mov ecx,@i
mov edx,@n[ecx]
mov eax,@n[ecx+4]
jmp @B_cout endp
_main proc

LOCAL @num1
LOCAL @num2

pushad

invoke GetTickCount
mov ebx,eax ;用ebx做时钟计数

xor edi,edi ;用edi做计数器

push 1
pop @num1
push 99
pop @num2

.while @num1 < 50
invoke _cout,@num1,@num2,0,0,0,0,0,0,0,0,0,0,0,4
inc edi
inc @num1
dec @num2
.endw

invoke GetTickCount
sub eax,ebx

invoke wsprintf,addr tmpstr,addr fmt_result,edi,eax
invoke MessageBox,NULL,addr tmpstr,NULL,MB_OK

popad
ret_main endp
start:
invoke GetModuleHandle,NULL
mov hInstance,eax
invoke _main
invoke ExitProcess,NULL
end start

调试易

一个关于从1到100的加法算法

解决方案 »