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

  • 主题发起人 主题发起人 fivewave
  • 开始时间 开始时间
F

fivewave

Unregistered / Unconfirmed
GUEST, unregistred user!
如：1353749
输出：1＋9
1＋5＋4
3＋7
3＋3＋4 。。等
数字串长度不限，可重复的数字，但结果中不能有重复输出！
 
呵呵,"结果中不能有重复输出"还是能饶了一下的.
串中不会出现0吧?
 
当然会出现0呀！而且可以不只一个0的。
我说的重复输出是 如果出现了 3＋7就不能输出7＋3了，呵呵！
如果串中有两个3的话，当然就输出 两个3＋7了呀！
 
呵呵，那就简单多了.
等我一会儿
 
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
 
这个问题很难啊，如果没有简便算法，需要全排列
至少计算10^10计算出全排列。如果出现重复的数字那......
将每一个排列计算看是否符合条件，如果符合需要查询是否已经存在
同样如果出现重复的数字那.......
哪位大虾能想出好办法，期待中！
 
已经发现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.
 
to LeeChange
Input s: 123456
1 2 3 4
1 3 6
1 4 5
2 3 5
4 6
只计算出一部分！还有很多
 
不行呀
报异常呀
 
呵呵,看看.
 
自己发现了个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.
 
如果随便输入就报异常了
输123456就没事！
to：ligia
结果是对的呀，怎么会还有很多呢？？？
 
to fivewave:
用我最后贴的程序.
用哪组数据异常,请提供,我好调试.
 
6 1 1 1 1
5 1 1 1 1 1
5 5
....
不是吗
 
to ligia:
一个数字只能用一遍.
 
如果随便输入就报异常了
输123456就没事！
to：ligia
结果是对的呀，怎么会还有很多呢？？？
 
to fivewave:
你输入什么字符串报异常了.干嘛不肯告诉我.
 
这下对了！呵呵
不过不太看得懂，能不能讲讲算法。马上给分
我改用c写！
 
就是深度优先.
如果你原来没接触过在这里不太容易讲清楚.
 
不好意思，原来我理解错误阿！
 
您必须登录或注册才可回复。

Similar threads

Ray
[转]终于可以发布Delphi下收点OSGI精髓皮毛而设计的插件框架WisdomPluginFramework
回复
4
查看
4K
chlkuei
C
快
100分继续挑战算法高手（50分求购算法的续集）up有分 (100分)
回复
13
查看
512
快刀不快
快
X
由给定字符串生成新字符串(100分)
回复
11
查看
519
xbl
X
W
请教一个算法(50分)
回复
4
查看
529
testnet
T
Y
如何从任意个数中抽取出任意个数的全部组合。(200分)
回复
7
查看
457
yuleibo
Y
后退
顶部