穷举法算法求解,要求速度要快。(200分)

Z

zl

Unregistered / Unconfirmed
GUEST, unregistred user!
算法求解
给定如下的参数:
1、字符型数组 如:[0..9,a..z,A..Z]
2、长度 :byte;
请在给定的字符数组中,穷举出长度小于给定长度值的字符组合(字符串)。
不能有重复。
提供算法的都有分,算法速度最快的分最高!!
 

笑傲江湖

Unregistered / Unconfirmed
GUEST, unregistred user!
补充一句,诸位提供算法时,速度第二,安全第一,千万不要把人家机器搞死掉啦:)
 
L

liersbaby

Unregistered / Unconfirmed
GUEST, unregistred user!
Z

zl

Unregistered / Unconfirmed
GUEST, unregistred user!
诸位不要被笑傲江湖给吓住了,如果你有好的解法,尽管大胆提出,
你的高见是我们每个人所期待的。^_^
 
B

beta

Unregistered / Unconfirmed
GUEST, unregistred user!
摘自 daiqingbo 以前的回答:

unit Unit1;
interface
uses
Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
StdCtrls;
type
TForm1 = class(TForm)
Memo1: TMemo;
Button1: TButton;
procedure Button1Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
procedure p(n: integer);
var
Form1: TForm1;
implementation
{$R *.DFM}
procedure p(n: integer)

var
fact: longint
//储存n!
o: array of integer
//储存递增进制输出
op: string
//储存字符串输出
i: longint;
symbol: array of string
//储存排列的元素,如1,2,3,4,5 或者a,b,c,d,e等,目前用前者
//当然可以很容易地改变成你所需要的 (beta注)
procedure inctostring
//递增进制数到字符串输出
var i, j: integer;
begin
op := '';
for i := 0 to n - 1 do
symbol := inttostr(i + 1)
//存入 1,2,3,4,5 ...
for i := 0 to n - 1 do
begin
op := op + symbol[o];
for j := o to n - 2 - i do
symbol[j] := symbol[j + 1];
end;
end;

procedure arrange
//处理进位
var i: integer;
begin
for i := n - 2 downto 0 do
if o = n - i then
begin
o := 0;
o[i - 1] := o[i - 1] + 1;
end;
end;

begin
setlength(symbol, n);
setlength(o, n);
fact := 1;
for i := 2 to n do
fact := fact * i
//fact:=n!
inctostring
//o 缺省为全为0
form1.memo1.lines.add(op)
//要改变输出,请修改这一句
for i := 1 to fact - 1 do
begin
o[n - 2] := o[n - 2] + 1;
arrange;
inctostring;
form1.memo1.lines.add(op)
//要改变输出,请修改这一句
end;
end;

procedure TForm1.Button1Click(Sender: TObject);
begin
memo1.Clear;
p(6)

end;

end.
 
Z

zl

Unregistered / Unconfirmed
GUEST, unregistred user!
感谢beta兄在半夜里还给我发贴子,我现在研究一下这段代码,
不过我粗看不下,好象不是我想要的,我的意思如下:
给定一下字符串常量
const
s='abcdefghijklmnopqrstuvwxyz0123456789';
var
len:byte;
请按s中的字符组合新的字符串,要求1:新字符的长度<len
要求2:要求全部穷举完且不能有重复。
(当然beta兄提供的算法如果改动一下可能也行,希望大家在beta兄的基础上按我的要求
再献计献策)。
 
Z

zl

Unregistered / Unconfirmed
GUEST, unregistred user!
请按s中的字符组合新的字符串,要求1:新字符的长度<len
要求2:要求全部穷举完且不能有重复。
(当然beta兄提供的算法如果改动一下可能也行,希望大家在beta兄的基础上按我的要求
再献计献策)。
 
Z

zl

Unregistered / Unconfirmed
GUEST, unregistred user!
请按s中的字符组合新的字符串,要求1:新字符的长度<len
要求2:要求全部穷举完且不能有重复。
(当然beta兄提供的算法如果改动一下可能也行,希望大家在beta兄的基础上按我的要求再献计献策)。
 
Z

zl

Unregistered / Unconfirmed
GUEST, unregistred user!
要求1:新字符的长度<len
要求2:要求全部穷举完且不能有重复。
 
Z

zl

Unregistered / Unconfirmed
GUEST, unregistred user!
请按s中的字符组合新的字符串,要求1:新字符的长度小于给定的长度
要求2:要求全部穷举完且不能有重复。
(当然beta兄提供的算法如果改动一下可能也行,希望大家在beta兄的基础上按我的要求
再献计献策)。

这个论坛有BUG,就是发出的贴子中不能有“<”号,刚才我发了几次就是这个原因,请大家见谅。
 
C

Chenlili

Unregistered / Unconfirmed
GUEST, unregistred user!
是不是排列组合的问题,如果是的话,用递归最快。
如果是的话说一声,程序马上到。
 
Z

zl

Unregistered / Unconfirmed
GUEST, unregistred user!
多谢Chenlili,把Code贴出来吧
 
I

Iknow

Unregistered / Unconfirmed
GUEST, unregistred user!
s相当于array [1..length(s)] of char;
可以用递归的方法来实现你的要求, 递归中止条件有2:
1. s中的元素都用过
2. 得到的长度(递归次数)满足要求的长度

大致如下:

savestring:string;

function FillChar(ss:string{剩下的字符集合};kkk:integer{剩下的长度}):integer;
var sss:string
i:integer
//下标
j:integer;
begin
if (length(ss)<=0) then
begin
{无数据, 退出}
result:=-1;
exit;
end;

if kkk<=0 then
begin
{满足条件}
result:=1;
exit;
end;

{否则就递归}
i:=1;
j:=0;
while i<=length(ss) do
{
sss:=ss;
delete(sss, i, 1)
//**
savestring:=savestring+ss;
j=filechar(sss, kkk-1);
if j>0 then
begin
{得到一个结果}
{显示或保存savestring}
{继续下一个}
delete(savestring, length(savestring), 1);
j=0;
end;
inc(i);
}

result:=0;

end;


程序没有调试过, 你试试看.
该程序是不允许有相同字符的, 即不出现aaaaa这类的
如果要相同字符的, 只要注释掉//**那行就可以了
 
C

Chenlili

Unregistered / Unconfirmed
GUEST, unregistred user!
来了!
const s='abcdefghijkk';
m = 4

var
bi : array [1..20] of 0..1;
re : array [1..20] of char;
t : string;
procedure move(n:integer);
var i : byte;
begin
if (n<=2) then begin
for i:=1 to 4 do
begin
if bi=0 then
begin
bi:=1;
re[n]:=s;
move(n+1);
// re:=s[n];
bi:=0;
end;
end;
end
else begin t:= ''
for i:=1 to 2 do t:=t+re
ListBox1.Items.Add(t);end;
end;
begin
fillchar(bi,sizeof(bi),0);
listbox1.Clear;
move(1);
Caption := IntToStr(ListBox1.Items.Count);
end;

然后如何取不同长度的值就不用我多写了吧。
 
Z

zl

Unregistered / Unconfirmed
GUEST, unregistred user!
多人接受答案了。
 
G

GGCAT

Unregistered / Unconfirmed
GUEST, unregistred user!
根本称不上是算法 因为太简单的 几个循环搞定
可是结果太大了 '012..9ABC.....XYZ' 长度为 6 时就能让你的硬盘
爆满 36的6次方 还能用递归求吗?
 
I

Iknow

Unregistered / Unconfirmed
GUEST, unregistred user!
GGCAT: 当抽取的长度不定时, 是无法事先确定循环次数的.

而且就算是36, 最深的递归也不过是6层, 而每次递归的堆栈使用也不过是

(sizeof(stringparam)+1)*2+sizeof(int)*2+n+o
= 37*2+4*2+n+o

其中n为其余的局部变量所占的空间大小, o为对象调用所占的系统开销.
就算n=100, o=1K, 也不过2K不到的空间, 乘6才多少? ^_^

不要以为递归就耗内存, 关键是递归中没有分配大内存的地方, 也没有死递归的条件.
 

笑傲江湖

Unregistered / Unconfirmed
GUEST, unregistred user!
问一个常识:把机器搞死只有耗尽内存一种姿势吗?
 

Similar threads

回复
0
查看
851
不得闲
X
回复
0
查看
619
xalion
X
S
回复
0
查看
947
SUNSTONE的Delphi笔记
S
S
回复
0
查看
768
SUNSTONE的Delphi笔记
S
顶部