1000分请教一个小算法 ( 积分: 300 )

A

Adnil

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-09-28

• #1

问题描述如下：
1. 数组A长度为7，里面存'a','b','c','d','e','f','g'
2. 数组B长度<=7，数据由用户输入，为数组A的子集，例如{'b','a','e','c','g'}, {'e','f','c'}
3. 现在要求输出长度为7的数组C，数组C的数据顺序要求在满足数组B的前提下尽量满足数组A

例如：
1. 输入{'b','a','e','c','g'}
输出b,a,e,c,d,f,g
2. 输入{'e','f','c'}
输出a,b,d,e,f,c,g
3. 输入{'f','b'}
输出a,f,b,c,d,e,g

 

E

errorcode

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-09-28

• #2

没看出你的例子的规律来。

第2，3，输入为子集，然后子集左右进行insert,第1的例子就看不懂了。

 

A

Adnil

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-09-28

• #3

就是保证数组B顺序的同时，兼顾数组A的顺序生成数组C

 

Y

yzdiyu

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-09-28

• #4

2为什么不是a,b,e,f,c,d,g
你的规律都不明确，如果人都不能描述，让计算机怎么描述？

 

A

Adnil

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-09-28

• #5

答案并不是唯一的,a,b,e,f,c,d,g同样满足答案.

 

E

errorcode

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-09-28

• #6

>>保证数组B顺序的同时，兼顾数组A的顺序
你第一例子并没保证数组B的顺序啊。

按你的描述：
输入{'b','a','e','c','g'}
输出应该是：b,a,e,c,g,d,f

 

C

cjqxyop

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-09-28

• #7

题目的实质是不是可以这样理解，保证B的顺序的同时，所产生的数组C的逆序数最小。（把A数组看成是一顺序数组）
如果是这样的话，这个问题就不是很难了
首先A-B，然后将得到的数组INSERT到B中 取逆序数最小的 就可（算法的消耗很大，但是可以优化，就是考虑的要细点）

 

A

ANiDelphi

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-09-28

• #8

我来试试
type
TMyAry = array[0..6] of Char;

function IndexOf(const C: Char
const Ary: array of Char): Integer;
begin
for Result := Low(Ary) to High(Ary) do
if Ary[Result] = C then Exit;
Result := -1;
end;

function GetArray(const Ary: array of Char): TMyAry;

function InvalidAry: Boolean;
const
ValidChars: set of Char = ['a'..'g'];
var
I: Integer;
begin
Result := True;
if Length(Ary) > 7 then Exit;
for I := Low(Ary) to High(Ary) do
if not (Ary in ValidChars) then Exit;
Result := False;
end;

var
C: Char;
I, J, Idx: Integer;
begin
if InvalidAry then Exit;
FillChar(Result, Length(Result), 0);
Idx := 0;
for C := 'a' to 'g' do
begin
I := IndexOf(C, Ary);
if I = -1 then
begin
Result[Idx] := C;
Inc(Idx);
end
else for J := 0 to I do
if IndexOf(Ary[J], Result) = -1 then
begin
Result[Idx] := Ary[J];
Inc(Idx);
end;
end;
end;

{ 测试 }
procedure TForm1.Button1Click(Sender: TObject);
var
Ary: TMyAry;
I: Integer;
S: string;
begin
Ary := GetArray(['e', 'f', 'c']);
S := '';
for I := Low(Ary) to High(Ary) do
S := S + Ary;
ShowMessage(S);
end;

 

L

liugaohui

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-09-29

• #9

基本上不知道什么意思

 

K

kingsonchan

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-10-25

• #10

保证、兼顾都是有歧义的描述，计算机要精确的描述。

 

Z

zdfcqu

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-10-26

• #11

1和2，3好像有点矛盾了哇？

 

X

xibaixin

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-11-01

• #12

看不出规律,

 

Z

zhksoft1

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-11-01

• #13

就是保证数组B顺序的同时，兼顾数组A的顺序生成数组C ？
顺序读输入串，先在B中查后在A中查是否有该字符，有，输出，没有先输出B中该字符以前的字符，再输出A中该字符以前的且B中没有字符。这样是不是？

 

W

wan_yi

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2007-11-02

• #14

//用TStringList吧，需要6行程序
//这样你的数据可以不止一个字符，也不一定是7个
function GetList(var LA,LB: TStringList): TStringList;
var
i: Integer;
begin
Result := TStringList.Create;
for i := 0 to LA.Count - 1 do LA := LA + '=' + IntToStr(i)

//记住LA的序号
for i := 0 to LB.Count - 1 do LA.Values[LB] := IntToStr(i)

//记住根据LB的序号改变LA的序号
for i := 0 to LA.Count - 1 do Result.Add(LA.ValueFromIndex + '=' + LA.Names)

//返回时把序号放在前面
Result.Sort

//根据序号排序
for i := 0 to Result.Count - 1 do Result := Result.ValueFromIndex

//去掉序号
end;

//测试：
procedure TForm1.FormCreate(Sender: TObject);
var
ListA,ListB,ListC: TStringList;
begin
ListA := TStringList.Create;
ListB := TStringList.Create;
ListA.CommaText := 'a,e,d,b,f,c,g';
ListB.CommaText := 'g,f,c';
ListC := GetList(ListA,ListB);
ShowMessage(ListC.Text)
//返回：a g e f c d b
ListA.Free;
ListB.Free;
ListC.Free;
end;

我的分数太少了，别忘了给分，不好意思...