算法求救：输出一个数字串中，所有和为10的组合！！(100分)

F

fivewave

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-29

• #1

如：1353749
输出：1＋9
1＋5＋4
3＋7
3＋3＋4 。。等
数字串长度不限，可重复的数字，但结果中不能有重复输出！

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-29

• #2

呵呵,"结果中不能有重复输出"还是能饶了一下的.
串中不会出现0吧?

 

F

fivewave

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-29

• #3

当然会出现0呀！而且可以不只一个0的。
我说的重复输出是 如果出现了 3＋7就不能输出7＋3了，呵呵！
如果串中有两个3的话，当然就输出 两个3＋7了呀！

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-29

• #4

呵呵，那就简单多了.
等我一会儿

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-29

• #5

program Project1;
{$APPTYPE CONSOLE}
uses
SysUtils;
const
MaxLength = 65535;
type
TNode = record
Used: array [1..MaxLength] of Boolean;
Sum: Byte;
d: Integer
end;

var
Num: array [1..MaxLength] of Byte;
Len: Integer;
Stack: array [1..10] of TNode;
Top: Integer;
Node: TNode;
procedure Init;
var
s: string;
i: Integer;
begin
Write('Input s: ');
ReadLn(s);
Len:=Length(s);
if Len>MaxLength then
begin
WriteLn('Too length!');
Halt
end;
for i:=1 to Lendo
begin
Num:=Ord(s)-Ord('0');
if Num>9 then
begin
WriteLn('Input error!');
Halt
end
end;

Top:=1;
FillChar(Stack[Top].Used, SizeOf(Stack[Top].Used), 0);
Stack[Top].Sum:=0;
Stack[Top].d:=0
end;

procedure Print(Node: TNode);
var
i: Integer;
begin
for i:=1 to Lendo
if Node.Used then
Write(Num, ' ');
WriteLn
end;

begin
Init;
while Top>0do
begin
while Stack[Top].d<Lendo
begin
Inc(Stack[Top].d);
if not Stack[Top].Used[Stack[Top].d] then
begin
Node.Sum:=Stack[Top].Sum+Num[Stack[Top].d];
if Node.Sum=10 then
begin
Node.Used:=Stack[Top].Used;
Node.Used[Stack[Top].d]:=True;
Print(Node)
end
else
if Node.Sum<10 then
begin
Inc(Top);
Stack[Top]:=Stack[Top-1];
Stack[Top].Used[Stack[Top].d]:=True;
Stack[Top].Sum:=Stack[Top].Sum+Num[Stack[Top].d]
end
end
end;
Dec(Top)
end;
ReadLn
end.
多测试测试,可能有Bug

 

L

ligia

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-29

• #6

这个问题很难啊，如果没有简便算法，需要全排列
至少计算10^10计算出全排列。如果出现重复的数字那......
将每一个排列计算看是否符合条件，如果符合需要查询是否已经存在
同样如果出现重复的数字那.......
哪位大虾能想出好办法，期待中！

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-29

• #7

已经发现Bug.改正如下:
program Project1;
{$APPTYPE CONSOLE}
uses
SysUtils;
const
MaxLength = 65535;
type
TNode = record
Used: array [1..MaxLength] of Boolean;
Sum: Byte;
d: Integer
end;

var
Num: array [1..MaxLength] of Byte;
Len: Integer;
Stack: array [1..10] of TNode;
Top: Integer;
procedure Init;
var
s: string;
i: Integer;
begin
Write('Input s: ');
ReadLn(s);
Len:=Length(s);
if Len>MaxLength then
begin
WriteLn('Too length!');
Halt
end;
for i:=1 to Lendo
begin
Num:=Ord(s)-Ord('0');
if Num>9 then
begin
WriteLn('Input error!');
Halt
end
end;

Top:=1;
FillChar(Stack[Top].Used, SizeOf(Stack[Top].Used), 0);
Stack[Top].Sum:=0;
Stack[Top].d:=0
end;

procedure Print(Node: TNode);
var
i: Integer;
begin
for i:=1 to Lendo
if Node.Used then
Write(Num, ' ');
WriteLn
end;

begin
Init;
while Top>0do
begin
while Stack[Top].d<Lendo
begin
Inc(Stack[Top].d);
if not Stack[Top].Used[Stack[Top].d] then
begin
Inc(Top);
Stack[Top]:=Stack[Top-1];
Stack[Top].Used[Stack[Top].d]:=True;
Stack[Top].Sum:=Stack[Top].Sum+Num[Stack[Top].d];
if Stack[Top].Sum=10 then
Print(Stack[Top])
end
end;
Dec(Top)
end;
ReadLn
end.

 

L

ligia

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-29

• #8

to LeeChange
Input s: 123456
1 2 3 4
1 3 6
1 4 5
2 3 5
4 6
只计算出一部分！还有很多

 

F

fivewave

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-29

• #9

不行呀
报异常呀

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-29

• #10

呵呵,看看.

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-29

• #11

自己发现了个Bug,但不是修正123456这组数据的.
请问,123456一共有多少组解?
program Project1;
{$APPTYPE CONSOLE}
uses
SysUtils;
const
MaxLength = 1000;
type
TNode = record
Used: array [1..MaxLength] of Boolean;
Sum: Byte;
d: Integer
end;

var
Num: array [1..MaxLength] of Byte;
Len: Integer;
Stack: array [1..MaxLength] of TNode;
Top: Integer;
procedure Init;
var
s: string;
i: Integer;
begin
Write('Input s: ');
ReadLn(s);
Len:=Length(s);
if Len>MaxLength then
begin
WriteLn('Too length!');
Halt
end;
for i:=1 to Lendo
begin
Num:=Ord(s)-Ord('0');
if Num>9 then
begin
WriteLn('Input error!');
Halt
end
end;

Top:=1;
FillChar(Stack[Top].Used, SizeOf(Stack[Top].Used), 0);
Stack[Top].Sum:=0;
Stack[Top].d:=0
end;

procedure Print(Node: TNode);
var
i: Integer;
begin
for i:=1 to Lendo
if Node.Used then
Write(Num, ' ');
WriteLn
end;

begin
Init;
while Top>0do
begin
while Stack[Top].d<Lendo
begin
Inc(Stack[Top].d);
if not Stack[Top].Used[Stack[Top].d] then
begin
Inc(Top);
Stack[Top]:=Stack[Top-1];
Stack[Top].Used[Stack[Top].d]:=True;
Stack[Top].Sum:=Stack[Top].Sum+Num[Stack[Top].d];
if Stack[Top].Sum=10 then
Print(Stack[Top])
end
end;
Dec(Top)
end;
ReadLn
end.

 

F

fivewave

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-29

• #12

如果随便输入就报异常了
输123456就没事！
to：ligia
结果是对的呀，怎么会还有很多呢？？？

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-29

• #13

to fivewave:
用我最后贴的程序.
用哪组数据异常,请提供,我好调试.

 

L

ligia

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-29

• #14

6 1 1 1 1
5 1 1 1 1 1
5 5
....
不是吗

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-29

• #15

to ligia:
一个数字只能用一遍.

 

F

fivewave

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-29

• #16

如果随便输入就报异常了
输123456就没事！
to：ligia
结果是对的呀，怎么会还有很多呢？？？

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-29

• #17

to fivewave:
你输入什么字符串报异常了.干嘛不肯告诉我.

 

F

fivewave

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-29

• #18

这下对了！呵呵
不过不太看得懂，能不能讲讲算法。马上给分
我改用c写！

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-29

• #19

就是深度优先.
如果你原来没接触过在这里不太容易讲清楚.

 

L

ligia

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-29

• #20

不好意思，原来我理解错误阿！