Algorithm 版 (精华区)

发信人: ssos (存在与虚无·戒酒戒网), 信区: Algorithm
标  题: [合集]请ACM队员做一下这个题...
发信站: 哈工大紫丁香 (2001年08月07日09:59:59 星期二), 站内信件


────────────────────────────────────────
 sino (茶水先生)                      于 2001年08月06日19:50:49 星期一 说道:

整数拆分：将一个正整数n,拆分成一组小于n的正整数的和（不考虑排列）。求
    共有多少组可能的拆分。
请谈谈思路。

────────────────────────────────────────
 ssos (存在与虚无·戒酒戒网)          于 2001年08月06日20:06:13 星期一 说道:

n的上限是多少？

────────────────────────────────────────
 sino (茶水先生)                      于 2001年08月06日20:08:28 星期一 说道:

可以认为是100

────────────────────────────────────────
 ssos (存在与虚无·戒酒戒网)          于 2001年08月06日20:12:57 星期一 说道:

100搜索就可以吧

────────────────────────────────────────
 lizhenguo (夸父·追日)               于 2001年08月06日20:21:05 星期一 说道:

组合数学的问题，以下为我摘自吴文虎组合数学一书的文章：
通过搜索的方法解决。我们采用回溯法搜索其和为M的k项数值，搜索
顺序由第一项至第k项。为了避免由交换律产生的重复方案，我们分别
设定1，2，。。。，M作为第1项的值，并按数值递增的顺序依次搜索
以后各项的值。具体地说，若当前拆分方案的首项值为J（1〈=J〈=M）
，前STEP（1〈=STEP〈=k）项的值已经选定，第STEP项的值为INDEX，
接下去，我们则在INDEX。。。[M/k]中选择一个与前STEP项的数和相
加后还小于等于M的值I，设定STEP+1的值为I。。。。依次类推，直至
设定k项数值的数和为M为止。这样回溯搜索一次，便枚举了首项值为J
的所有拆分方案；回溯搜索M次，所有不重复的拆分方案边自然完全产生
出来了。
Program Problem1;
Const maxm=100;
Var k,M:integer;
    Ans:array[1..Maxm] of integer;
    Total:integer;
procedure print;
  var i:integer;
  begin
    inc(total);
    write('Ans No.',total:4,':');
    for i:=1 to k-1 do write(ans[i],'+');
    writeln(ans[k],'=',m);
  end;
procedure Solve(step,index,sum:integer);
var i:integer;
begin
  if step=k then
    if sum=m then print else
  else
  for i:=index to m do
    if sum+i<=m then
      begin
        ans[step+1]:=i;
        solve(step+1,i,sum+i);
      end;
end;
begin
  repeat write('M=');
    read(m)
  until m in [1..maxm];
  reapeat write('k=');
    read(k)
  until k in [1..m];
  total:=0;
  for i:=1 to m div k do
    begin
      ans[1]:=i;
      solve(1,i,i)
    end;
  readln;
end.

────────────────────────────────────────
 lizhenguo (夸父·追日)               于 2001年08月06日20:36:36 星期一 说道:

看了一下效率好象不高。

────────────────────────────────────────
 ssos (存在与虚无·戒酒戒网)          于 2001年08月06日20:37:24 星期一 说道:

你的复杂度是多少
我有时间复杂度为o(n^2)的算法

────────────────────────────────────────
 ssos (存在与虚无·戒酒戒网)          于 2001年08月06日20:38:02 星期一 说道:

就是不能证明正确性

────────────────────────────────────────
 sino (茶水先生)                      于 2001年08月06日20:58:50 星期一 说道:

我有方法，不过还要看看其他队员。请师兄讲讲看法先。

────────────────────────────────────────
 lizhenguo (夸父·追日)               于 2001年08月06日21:07:55 星期一 说道:

wait
我的程序正准备出炉

────────────────────────────────────────
 ssos (存在与虚无·戒酒戒网)          于 2001年08月06日21:12:03 星期一 说道:

把结论贴出来吧

────────────────────────────────────────
 lizhenguo (夸父·追日)               于 2001年08月06日21:14:40 星期一 说道:

program chaifen;
{$APPTYPE CONSOLE}
uses SysUtils;
var
  xl:array[0..100] of integer;
  add:array[0..100] of integer;
  i,j:integer;
  m,k:integer;
  total:integer;
procedure print;
  var
    i:integer;
  begin
    for i:=1 to k do
      write(xl[i]);
    writeln;
  end;
procedure find(step:integer);
  var
    i,j:integer;
    min:integer;
  begin
    min:=(m-add[step-1]) div (k-step+1);
    if (m-add[step-1]) mod (k-step+1)>0 then inc(min);
    if step=k then exit;
    while xl[step]>min do
      begin
        dec(xl[step]);
        inc(xl[step+1]);
        if xl[step+1]<=xl[step] then
          begin
            print;
            inc(total);
          end;
        dec(add[step]);
        find(step+1);
      end
  end;
begin
  write('M=');
  readln(m);
  write('k=');
  readln(k);}
  add[0]:=0;
  xl[1]:=m-(k-1);
  add[1]:=xl[1];
  for i:=2 to k do
    begin
      xl[i]:=1;
      add[i]:=add[i-1]+1;
    end;
  total:=1;
  print;
  find(1);
  writeln('total=',total);
  readln;
end.
在delphi5.0下编译通过

────────────────────────────────────────
 ssos (存在与虚无·戒酒戒网)          于 2001年08月06日21:15:37 星期一 说道:

faint
结果是多少
对一下

────────────────────────────────────────
 lizhenguo (夸父·追日)               于 2001年08月06日21:27:51 星期一 说道:

我先解释一下吧。
设有数组xl存放拆分。
另有数组add存放前i项的和
如当m=10,k=4时，一开始xl为：
7 1 1 1
add为：
7 8 9 10
为了避免重复，规定一条，前面的数不比后面的小，即xl[i]>=xl[j] i>j
则可以得出xl[i] i=1,2,3,...k的最小值为
                             1      (m-add[i-1]) mod (k-step+1)>0
(m-add[i-1]) div (k-step+1)+ 0      (m-add[i-1]) mod (k-step+1)=0
这样只要当xl[i]大于最小值时，还可以继续往后面调整，直到当调整
好且满足前面的规定时，就可以输出了
当
m=10 k=4时
7 1 1 1
6 2 1 1
5 3 1 1
5 2 2 1
4 3 2 1
4 2 2 2
3 3 2 2

────────────────────────────────────────
 sino (茶水先生)                      于 2001年08月06日21:28:52 星期一 说道:

还是枚举法.....

────────────────────────────────────────
 ssos (存在与虚无·戒酒戒网)          于 2001年08月06日21:29:12 星期一 说道:

好像你和sino的题意不太一样
算算100,0的情况

────────────────────────────────────────
 lizhenguo (夸父·追日)               于 2001年08月06日21:30:17 星期一 说道:

他的是k从1到m的全部情况
只要来个循环即可

────────────────────────────────────────
 lizhenguo (夸父·追日)               于 2001年08月06日21:30:42 星期一 说道:

not 枚举 but 回溯

────────────────────────────────────────
 ssos (存在与虚无·戒酒戒网)          于 2001年08月06日21:34:21 星期一 说道:

faint
枚举和回溯的复杂度是一样的

────────────────────────────────────────
 lizhenguo (夸父·追日)               于 2001年08月06日21:35:51 星期一 说道:

回溯可以剪纸，但枚举只能判断当前枚举值是否可行。

────────────────────────────────────────
 lizhenguo (夸父·追日)               于 2001年08月06日21:36:11 星期一 说道:

可以试一下100 80

────────────────────────────────────────
 ssos (存在与虚无·戒酒戒网)          于 2001年08月06日21:38:02 星期一 说道:

100溢出了:(

────────────────────────────────────────
 lizhenguo (夸父·追日)               于 2001年08月06日21:40:11 星期一 说道:

100 0当然不行拉。k>=1
不然我改一下程序，适应sino的问题

────────────────────────────────────────
 sino (茶水先生)                      于 2001年08月06日21:42:26 星期一 说道:

//nod 有道理的说！

────────────────────────────────────────
 sino (茶水先生)                      于 2001年08月06日21:42:57 星期一 说道:


────────────────────────────────────────
 ssos (存在与虚无·戒酒戒网)          于 2001年08月06日21:43:27 星期一 说道:

80是15796475
不知道对不对？

────────────────────────────────────────
 lizhenguo (夸父·追日)               于 2001年08月06日21:44:40 星期一 说道:

100 8597

────────────────────────────────────────
 sino (茶水先生)                      于 2001年08月06日21:45:12 星期一 说道:

15796475+1 is right !
多长时间？

────────────────────────────────────────
 ssos (存在与虚无·戒酒戒网)          于 2001年08月06日21:45:21 星期一 说道:

这个好像不对

────────────────────────────────────────
 lizhenguo (夸父·追日)               于 2001年08月06日21:45:24 星期一 说道:

5336

────────────────────────────────────────
 lizhenguo (夸父·追日)               于 2001年08月06日21:46:04 星期一 说道:

m=10
请给出一组正确的答案？

────────────────────────────────────────
 ssos (存在与虚无·戒酒戒网)          于 2001年08月06日21:46:59 星期一 说道:

来不及算时间了
3-4秒种把
这不是o(n^2)的算法
那个有问题

────────────────────────────────────────
 ssos (存在与虚无·戒酒戒网)          于 2001年08月06日21:47:12 星期一 说道:

41

────────────────────────────────────────
 sino (茶水先生)                      于 2001年08月06日21:47:42 星期一 说道:

see 1325!

────────────────────────────────────────
 lizhenguo (夸父·追日)               于 2001年08月06日21:48:35 星期一 说道:

给出一组拆分方案！
5 7
10 39

────────────────────────────────────────
 sino (茶水先生)                      于 2001年08月06日21:50:24 星期一 说道:

5:
1，1，1，1，1
1，1，1，2
1，1，3
1，4
1，2，2
2，3
5

────────────────────────────────────────
 sino (茶水先生)                      于 2001年08月06日21:50:54 星期一 说道:

10: 42!

────────────────────────────────────────
 lizhenguo (夸父·追日)               于 2001年08月06日21:56:57 星期一 说道:

5 相同，给出6的

────────────────────────────────────────