一个算法问题，我已经困惑了多时，清高手赐教（100分）(100分)

  • 主题发起人 主题发起人 jxyghm
  • 开始时间 开始时间
to redflyfox:
你的解法有问题，如果：
389 207 155 300 299 400 158 65
经过第一次运算得出序列：
结果1 7 4 1 4 3 3 1 0
再进行排序,相同的取高度大的，得出：
结果2：389 300 400 158 65
那么问题1的答案是打下以下导弹（0：打下，X：不打）：
0 X X 0 X 0 0 0
这个解显然是错误的。
 
我想了个算法，不知道有没有问题，大家帮忙看看：
9个数值：
原序列： 10 8 9 7 5 6 4 3 2
数值后可跟数字个数： 8 7 6 5 4 3 2 1 0
进行排序得到：
排序后序列： 10 9 8 7 6 5 4 3 2
数值后可跟数字个数： 8 7 6 5 4 3 2 1 0
按照可跟数字个数最少的原则可得：
10 --> 8
9 --> 6
8 --> 6 (按照个数一样取大数值原则，8不取）
7 --> 5
6 --> 3
5 --> 3 (按照个数一样取大数值原则，5不取）
4 --> 2
3 --> 1
2 --> 0
得到序列：10 9 7 6 4 3 2 为最长的降序序列
（当然就这个问题有多解，不过这种解法只能解出一个）。
不知道可对？


 
按原题解：
原序列： 389 207 155 300 299 170 158 65
数值后可跟数字个数： 7 4 1 4 3 2 1 0
进行排序得到：
排序后序列： 389 300 299 207 170 158 155 65
数值后可跟数字个数： 7 6 5 4 3 2 1 0
按照可跟数字个数最少的原则可得：
389 --> 7
300 --> 4
299 --> 3
207 --> 4 (不取，因为4>3）
170 --> 2
158 --> 1
155 --> 1 (不取,因为1不小于1,而且155<158）
65 --> 0
得到序列：389 300 299 170 158 65 为最长的降序序列
 
数值后可跟数字个数： 7 4 1 4 3 2 1 0
怎么来的
 
比如 389，后面有7个数字比它小（207 155 300 299 170 158 65 ）
207，后面有4个数字比它小（155 170 158 65 ）
155，后面有1个数字比它小（65 ）
。。。
。。。
 
to chen_ke
我的算法确实有点问题，应该是在结果1的基础上排序，遇相同数值首先取比前一个数值小的，
然后再取其中较大的。

 
你的说法就是我所提出的算法是吗？
 
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls;
type
TForm1 = class(TForm)
Button1: TButton;
procedure Button1Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;

//TSomeNode = class ;
TSomeNode = class(TCollectionItem)
public
Brothers :TCollection ;
Child :TSomeNode ;
Parent :TSomeNode ;
AValue :Integer ;
constructor Create(Collection :TCollection) ;
destructor Destroy ;
override ;
end ;
proceduredo
it(AInput :array of integer) ;
var
Form1: TForm1;
implementation
{$R *.dfm}
proceduredo
it(AInput :array of integer) ;
var i :Integer ;
VirtualRoot :TSomeNode ;
CurrentRoot :TSomeNode ;
procedure InsertToRoot(AValue :Integer;var ARoot:TSomeNode) ;
var ANode :TSomeNode ;
i :Integer ;
founded :Boolean ;
begin
if Assigned(ARoot.Child) then
begin
if AValue <= ARoot.Child.AValue then
InsertToRoot(AValue,ARoot.Child) ;
if AValue > ARoot.Child.AValue then
begin
if ARoot.Brothers.Count > 0 then
begin
i := 0 ;
Founded := False ;
while i < ARoot.Brothers.Countdo
begin
ANode := TSomeNode(ARoot.Brothers.Items) ;
if AValue <= ANode.AValue then
begin
InsertToRoot(AValue,ANode) ;
founded := True ;
end ;
inc(i) ;
end ;
if not founded then
begin
ANode := TSomeNode(ARoot.Brothers.Add) ;
ANode.Brothers := TCollection.Create(TSomeNode) ;
ANode.Parent := ARoot ;
ANode.Child := nil ;
ANode.AValue := AValue ;
end ;
Exit ;
end else
begin
ANode := TSomeNode(ARoot.Brothers.Add) ;
ANode.Brothers := TCollection.Create(TSomeNode) ;
ANode.Parent := ARoot ;
ANode.Child := nil ;
ANode.AValue := AValue ;
Exit ;
end ;
end ;
end else
begin
ARoot.Child := TSomeNode.Create(nil) ;
ARoot.Child.Parent := ARoot ;
ARoot.Child.Child := nil ;
ARoot.Child.AValue := AValue ;
Exit ;
end ;
end ;
begin
VirtualRoot := TSomeNode.Create(nil) ;
VirtualRoot.AValue := 32767 ;
VirtualRoot.Parent := nil ;
CurrentRoot := VirtualRoot ;
i := Low(AInput) ;
while i < High(AInput)do
begin
InsertToRoot(AInput,CurrentRoot) ;
inc(i) ;
end ;
ShowMessage(IntToStr(VirtualRoot.Child.Brothers.count)) ;
end ;
{ TSomeNode }
constructor TSomeNode.Create(Collection: TCollection);
begin
inherited Create(Collection);
Brothers := TCollection.Create(TSomeNode) ;
Parent := nil ;
Child := nil ;
AValue := 0 ;
end;

procedure TForm1.Button1Click(Sender: TObject);
var AInput :Array [1..13] of Integer ;
begin
AInput[1] := 300 ;
AInput[2] := 200 ;
AInput[3] := 250 ;
AInput[4] := 210 ;
AInput[5] := 125 ;
AInput[6] := 220 ;
AInput[7] := 275 ;
AInput[8] := 110 ;
AInput[9] := 127 ;
AInput[10] := 55 ;
AInput[11] := 126 ;
AInput[12] := 278 ;
AInput[13] := 60 ;
do
it(AInput) ;
end;

destructor TSomeNode.Destroy;
begin
Brothers.Free ;
if Assigned(Child) then
Child.Free ;
inherited;
end;

end.
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls;
type
TForm1 = class(TForm)
Button1: TButton;
procedure Button1Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;

//TSomeNode = class ;
TSomeNode = class(TCollectionItem)
public
Brothers :TCollection ;
Child :TSomeNode ;
Parent :TSomeNode ;
AValue :Integer ;
constructor Create(Collection :TCollection) ;
destructor Destroy ;
override ;
end ;
proceduredo
it(AInput :array of integer) ;
var
Form1: TForm1;
implementation
{$R *.dfm}
proceduredo
it(AInput :array of integer) ;
var i :Integer ;
VirtualRoot :TSomeNode ;
CurrentRoot :TSomeNode ;
procedure InsertToRoot(AValue :Integer;var ARoot:TSomeNode) ;
var ANode :TSomeNode ;
i :Integer ;
founded :Boolean ;
begin
if Assigned(ARoot.Child) then
begin
if AValue <= ARoot.Child.AValue then
InsertToRoot(AValue,ARoot.Child) ;
if AValue > ARoot.Child.AValue then
begin
if ARoot.Brothers.Count > 0 then
begin
i := 0 ;
Founded := False ;
while i < ARoot.Brothers.Countdo
begin
ANode := TSomeNode(ARoot.Brothers.Items) ;
if AValue <= ANode.AValue then
begin
InsertToRoot(AValue,ANode) ;
founded := True ;
end ;
inc(i) ;
end ;
if not founded then
begin
ANode := TSomeNode(ARoot.Brothers.Add) ;
ANode.Brothers := TCollection.Create(TSomeNode) ;
ANode.Parent := ARoot ;
ANode.Child := nil ;
ANode.AValue := AValue ;
end ;
Exit ;
end else
begin
ANode := TSomeNode(ARoot.Brothers.Add) ;
ANode.Brothers := TCollection.Create(TSomeNode) ;
ANode.Parent := ARoot ;
ANode.Child := nil ;
ANode.AValue := AValue ;
Exit ;
end ;
end ;
end else
begin
ARoot.Child := TSomeNode.Create(nil) ;
ARoot.Child.Parent := ARoot ;
ARoot.Child.Child := nil ;
ARoot.Child.AValue := AValue ;
Exit ;
end ;
end ;
begin
VirtualRoot := TSomeNode.Create(nil) ;
VirtualRoot.AValue := 32767 ;
VirtualRoot.Parent := nil ;
CurrentRoot := VirtualRoot ;
i := Low(AInput) ;
while i < High(AInput)do
begin
InsertToRoot(AInput,CurrentRoot) ;
inc(i) ;
end ;
ShowMessage(IntToStr(VirtualRoot.Child.Brothers.count)) ;
end ;
{ TSomeNode }
constructor TSomeNode.Create(Collection: TCollection);
begin
inherited Create(Collection);
Brothers := TCollection.Create(TSomeNode) ;
Parent := nil ;
Child := nil ;
AValue := 0 ;
end;

procedure TForm1.Button1Click(Sender: TObject);
var AInput :Array [1..13] of Integer ;
begin
AInput[1] := 300 ;
AInput[2] := 200 ;
AInput[3] := 250 ;
AInput[4] := 210 ;
AInput[5] := 125 ;
AInput[6] := 220 ;
AInput[7] := 275 ;
AInput[8] := 110 ;
AInput[9] := 127 ;
AInput[10] := 55 ;
AInput[11] := 126 ;
AInput[12] := 278 ;
AInput[13] := 60 ;
do
it(AInput) ;
end;

destructor TSomeNode.Destroy;
begin
Brothers.Free ;
if Assigned(Child) then
Child.Free ;
inherited;
end;

end.
 
前面有点错误，现在改好了，两个问题都可能解决了，不知有没有错误，请大家批评指正
代码: 
unit Unit1;
interface
uses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
  StdCtrls, Grids;
type
  TForm1 = class(TForm)
    Button1: TButton;
    procedure Button1Click(Sender: TObject);
  Private
    { Private declarations }
  Public
    { Public declarations }
  end;

  TarrInt = array of Integer;
  TArrArrInt = array of TarrInt;
var
  Form1: TForm1;
  inA: Tarrint;
function GetBest(aai: Tarrint): TArrarrint;
function GetNum(aai: TArrint): Integer;
implementation
{$R *.DFM}
function GetNum(aai: TArrint): Integer;
var
  tmp: Tarrarrint;
  i, j, h, rlt: Integer;
  b: Boolean;
begin
  rlt := 0;
  while Length(aai) > 0do
  begin
    tmp := GetBest(aai);
    i := 0;
    while i <= High(aai)do
    begin
      b := False;
      for h := 0 to High(tmp[0])do
        if aai[i] = tmp[0, h] then
          b := True;
      if b then
      begin
        for j := i + 1 to High(aai)do
          aai[j - 1] := aai[j];
        setlength(aai, Length(aai) - 1);
        Dec(i);
      end;
      inc(i);
    end;
    inc(rlt);
  end;
  Result := rlt;
end;
function GetBest(aai: Tarrint): TArrarrint;
var
  i, j,h, maxa,ll: Integer;
  aaa: array of Tarrint;
  rlt: Tarrarrint;
begin
//389 207 155 300 299 170 158 65
  ll := Length(aai);
  setlength(aaa, ll*ll);
  for i := 0 to High(aai)do
    for h := 1 to High(aai)-ido
    begin
      setlength(aaa[i*Ll+h], 1);
      aaa[i*ll+h, 0] := aai[i];
      for j := i + h to High(aai)do
        if aai[j] <= aaa[i*ll+h,High(aaa[i*ll+h])] then
        begin
          setlength(aaa[i*ll+h], Length(aaa[i*ll+h]) + 1);
          aaa[i*ll+h, High(aaa[i*ll+h])] := aai[j];
        end;
    end;
  setlength(rlt, 0);
  maxa := 0;
  for i := 0 to High(aaa)do
    if maxa < Length(aaa[i]) then
      maxa := Length(aaa[i]);
  for i := 0 to high(aaa)do
    if Length(aaa[i]) = maxa then
    begin
      setlength(rlt, Length(rlt) + 1);
      rlt[High(rlt)] := aaa[i];
    end;
  Result := rlt;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  ss: tarrarrint;
  iii : Integer;
begin
  setLength(ina, 8);
  ina[0] := 389;
  ina[1] := 207;
  ina[2] := 155;
  ina[3] := 300;
  ina[4] := 299;
  ina[5] := 170;
  ina[6] := 158;
  ina[7] := 65;
  ss := GetBest(ina);
  iii := GetNum(ina);
  ShowMessage('有' + IntToStr(Length(ss)) + '种组合，最多可打下' + IntToStr(Length(ss[0])) + '导弹'#10#13'最少需要系统数为'+inttostr(iii));
end;

end.
 
接受答案了.
 
您必须登录或注册才可回复。

Similar threads

S
[转]ClientDataSet加上TDataSetProvider的数据保存问题
回复
0
查看
3K
SUNSTONE的Delphi笔记
S
S
[转]ClientDataSet加上TDataSetProvider的数据保存问题
回复
0
查看
2K
SUNSTONE的Delphi笔记
S
D
[原]Delphi XE4 For IOS真机调试配置教程
回复
0
查看
1K
DelphiTeacher的专栏
D
S
[iOS]在苹果手机上使用九宫格输入法时编辑框输入问题的一个临时解决方案
回复
0
查看
777
swish
S
D
[原]OrangeUI－Delphi移动开发利器
回复
0
查看
2K
DelphiTeacher的专栏
D
后退
顶部