一个朋友的面试题（有兴趣者请进） ( 积分: 0 )

A

AI_Player

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-09

• #21

实测了一下，我的算法通不过，因为只有一个数组，所以存在后效性，郁闷ing~

 

W

willing66

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-09

• #22

Dorice的算法是O，只是有错就是了，我只是修改了其中的错误
#include <iostream>
using namespace std;
void main()
{
int a[100];
int i, j, t;
for (i=0;
i<100;
i++)
{
a = i;
cout<<i<<&quot;
&quot;;
}
cout<<endl;
i=0;
j=99;
while (i<100 &amp;&amp;
j>=0)
{
while (i<100 &amp;&amp;
a%2==0 &amp;&amp;
i<j) {
i++;
}
while (j>=0 &amp;&amp;
a[j]%2!=0 &amp;&amp;
i<j) {
j--;
}
if (i<100 &amp;&amp;
j>=0) {
t=a;
a=a[j];
a[j]=t;
}
else
break;
i++;
j--;
}
for (i=0;
i<100;
i++)
{
cout<<a<<&quot;
&quot;;
}
cout<<endl;
}

 

L

lmk

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-09

• #23

小弟有个苯方法就是在数组的头和尾各设个指针！或者用下标也可以，然后前面的指针先开始往后查找第一个偶数，而后一个指针从后往前查找第一个奇数，当2个都查到了就进行一次交换，什么时候2个指针指向同一个数了！就停止查找！这样不是实现了奇数在前，偶数在后了吗！而指针所在的位置又可以作为分界点！然后对奇数和偶数分别排序！

 

T

tseug

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-09

• #24

大致的就是这样，思路慢慢再说[][]
type
ta = array[1..100] of Integer;
procedure n(var a: ta;
i: integer);
var
c : integer;
j,k : integer;
begin
k:=i;
c:=a[k];
repeat
if k<=50 then
j := k*2-1 else
j := (k-50) * 2;
a[k] := a[j];
k := j;
until j=i;
if odd(i) then
k := (i+1) div 2 else
k := 50 + i div 2;
a[k]:=c;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
a : ta;
i : Integer;
begin
for i:=1 to 100do
a:=i;
n(a,2);
n(a,4);
n(a,6);
n(a,10);
n(a,12);
n(a,16);
for i:=1to 100do
Memo1.Lines.Add(IntToStr(a));
end;

 

A

AI_Player

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-09

• #25

我怀疑楼主把题目弄错了

 

L

love751

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-10

• #26

偶数和奇数的先后顺序不改变吗?如果不改变那可是挺有难度

 

T

tseug

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-10

• #27

procedure TForm1.Button1Click(Sender: TObject);
var
a : ta;
i : Integer;
begin
for i:=1 to 100do
a:=i;
n(a,2);
n(a,4);
n(a,6);
n(a,10);
n(a,12);
n(a,16);
n(a,34);
for i:=1to 100do
Memo1.Lines.Add(IntToStr(a));
end;

上次了落了个n(a,34);

 

Y

yihanyan

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-10

• #28

我也想怀疑自己是不是把题目弄错了，又向朋友确认过，我是不行了，搞不出来，实在是太有难度

 

D

d_eng

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-10

• #29

我的你看过没有？符不符合要求？

 

J

jey

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-10

• #30

procedure TForm1.Button1Click(Sender: TObject);
const
conCount = 10;
var
a: array [0..conCount - 1] of Integer;
i,J: Integer;
n, k: Integer;

begin
//初始化数组 作者QQ: 344430663
Randomize;
Memo1.Clear;
Memo2.Clear;
J:=0;
for i := 0 to conCount - 1do
begin
a := Random(20) + 1;
Memo2.Lines.Add(IntToStr(a));
end;
//排序:奇数在前，偶数在后
k := 0;
for i := 0 to conCount - 1do
begin
if a mod 2 = 1 then
begin
j:=i;
if J=0 then
Continue;
while a[J-1]mod 2 = 0do
begin

n := a[J];
a[J]:=a[J-1];
a[J-1]:=n;
if J>=2 then
J:=j-1;
end;
J:=0;
end
else
begin
Inc(J);
end;
end;

//输出
Memo1.Lines.begin
Update;
try
Memo1.Clear;
for i := 0 to conCount - 1do
Memo1.Lines.Add(IntToStr(a))
finally
Memo1.Lines.EndUpdate;
end;
end;
end.
在此谢谢放飞,不行找我..

 

J

jey

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-10

• #31

只要是奇数就看前面是否是偶数,是就互换,真到为奇数为止.
why is god?

 

Y

ysai

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-10

• #32

想了一个方法,有点局限性
1.扫描数组,找到最大奇数x
2.扫描数组,令 偶数 y=y+x+1
3.排序
4.扫描数组,令 偶数 y=y-x-1

 

Y

ysai

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-10

• #33

楼主的意思是,原数组如果是
3,4,1,5,2
输出要为
3,1,5,4,2
???那就没想出好办法....

 

T

tseug

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-10

• #34

关键是他的算法要求O, 而且不允许用辅助空间[]

 

Y

yihanyan

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-10

• #35

to_eng
你的程序结果肯定没有问题，但是你的程序的时间复杂度不符合要求呀

 

T

tseug

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-10

• #36

我的可以，[][]

 

4

41426277

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-10

• #37

procedure TForm1.Button1Click(Sender: TObject);
const
conCount = 29;
var
ar:array[0..conCount-1] of integer;
i,n,z,m:integer;
begin
memo1.Clear;
//随机几个数
for i:=0 to conCount-1do
ar:=random(conCount-1);
for i:=0 to conCount-1do
memo1.Text:=memo1.Text+inttostr(ar)+',';
memo1.Text:=memo1.Text+#13#10;
//运算结果
for i:=0 to conCount-1do
if (ar and 1 =0) then
for n:=conCount-1do
wnto ido
if (ar[n] and 1 =1) then
begin
z:=ar;
ar:=ar[n];
ar[n]:=z;
break;
end;
//排序单数
m:=conCount div 2 - 1;
for i:=0 to mdo
for n:=mdo
wnto ido
if ar>ar[n] then
begin
z:=ar;
ar:=ar[n];
ar[n]:=z;
end;
//排序双数
m:=conCount div 2;
for i:=m to conCount-1do
for n:=conCount-1do
wnto ido
if ar<ar[n] then
begin
z:=ar;
ar:=ar[n];
ar[n]:=z;
end;
for i:=0 to conCount-1do
memo1.Text:=memo1.Text+inttostr(ar)+',';
end;

 

放

放飞

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-11

• #38

呵呵，终于明白LZ的问题了，这个程序应该可以满足你的要求了
//交换两个指针指向的整数
procedure jh(psi, pdi: PInteger);
var
tmp: Integer;
begin
tmp := psi^;
psi^ := pdi^;
pdi^ := tmp;
end;

function px(psi, pdi: PInteger;
n: Integer;
iCount: Integer): Boolean;
var
tmppdi: PInteger;
begin
Result := False;
if (psi^ mod 2) = 0 then
begin
if (pdi^ mod 2) = 1 then
jh(psi, pdi)
else
begin
if n < iCount - 2 then
begin
tmppdi := pdi;
Inc(tmppdi);
Result := px(pdi, tmppdi, n + 1, iCount);
if (n + 1 <> iCount - 1) then
jh(psi, pdi);
if n + 2 = iCount - 1 then
Result := True;
end
else
if n < iCount - 1 then
Result := True;
end;
end;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
i: Integer;
iCount: Integer;
a: array of Integer;
begin
Memo1.Clear;
try
iCount := StrToInt(Edit1.Text);
//Edit中输入数组的大小
except
iCount := 100;
end;
//初始化数组
SetLength(a, iCount);
Randomize;
for i := 0 to iCount - 1do
a := Random(iCount * 2) + 1;
//输出原始数组
PrintIntArray(@a[0], iCount);
//排序:奇数在前，偶数在后，并且不改变原来的顺序
for i := 0 to iCount - 2do
begin
if px(@a, @a[i + 1], i, iCount) then
Break;
end;

//输出排序后的数组
PrintIntArray(@a[0], iCount);
end;

procedure TForm1.PrintIntArray(pi: PInteger;
ACount: Integer);
var
i: Integer;
begin
Memo1.Lines.begin
Update;
try
for i := 0 to ACount - 1do
begin
Memo1.Lines.Add(IntToStr(pi^));
Inc(pi);
end;

Memo1.Lines.Add('*******************************')
finally
Memo1.Lines.EndUpdate;
end;
end;

 

差

差不多算了

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-11

• #39

哈哈，这么简单的问题，直接输出奇数和偶数不就可以了，还写这么多程序？？
不就是1到100吗？
for i:=1 to 100do
begin
//奇数
end;
for i:=1 to 100do
begin
//偶数
end;

不要想那么复杂，也许这样的题目就要简单的去想，不必去想那么复杂，哈哈

 

放

放飞

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-11-11

• #40

刚刚发布的那个有个错误，更正一下
//交换两个指针指向的整数
procedure jh(psi, pdi: PInteger);
var
tmp: Integer;
begin
tmp := psi^;
psi^ := pdi^;
pdi^ := tmp;
end;

function px(psi, pdi: PInteger;
n: Integer;
iCount: Integer): Boolean;
var
tmppdi: PInteger;
begin
Result := False;
if (psi^ mod 2) = 0 then
begin
if (pdi^ mod 2) = 1 then
jh(psi, pdi)
else
begin
if n < iCount - 2 then
begin
tmppdi := pdi;
Inc(tmppdi);
Result := px(pdi, tmppdi, n + 1, iCount);
if (n + 1 <> iCount - 1) and (pdi^ mod 2 = 1) then
jh(psi, pdi);
if n + 2 = iCount - 1 then
Result := True;
end
else
if n < iCount - 1 then
Result := True;
end;
end;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
i: Integer;
iCount: Integer;
a: array of Integer;
begin
Memo1.Clear;
try
iCount := StrToInt(Edit1.Text);
//Edit中输入数组的大小
except
iCount := 100;
end;
//初始化数组
SetLength(a, iCount);
Randomize;
for i := 0 to iCount - 1do
//a := Random(iCount * 2) + 1;
a := i + 1;
//输出原始数组
PrintIntArray(@a[0], iCount);
//排序:奇数在前，偶数在后，并且不改变原来的顺序
for i := 0 to iCount - 2do
begin
if px(@a, @a[i + 1], i, iCount) then
Break;
end;

//输出排序后的数组
PrintIntArray(@a[0], iCount);
end;

procedure TForm1.PrintIntArray(pi: PInteger;
ACount: Integer);
var
i: Integer;
begin
Memo1.Lines.begin
Update;
try
for i := 0 to ACount - 1do
begin
Memo1.Lines.Add(IntToStr(pi^));
Inc(pi);
end;

Memo1.Lines.Add('*******************************')
finally
Memo1.Lines.EndUpdate;
end;
end;