level 1
idealguy
楼主
题目如下:兔子小白是位数学爱好者,有一次它参加了兔界里的数学比赛,成绩公布后,小白很想知道自己的成绩到底排第几,现在请你帮它编一个程序,要求输入一个成绩,就能知道相应的名次。注意:同分的按相同名次算,且只算一次。 (百度知道)
网友提供了程序(略)。本人认为不够优化,给出优化后的程序。
该程序采用了以下方案:
1) 采用插入排序法对成绩表进行排序,去除重复项;采用对分搜索确定插入位置,效率高;
2) 可多次进行查询,查询采用对分搜索,效率高。被查询值可以是不在成绩表中的数值。
var
Sco:array[1..1000] of longint;
N,Ns:integer;
Function Bfind(j1,j2:Integer; A:Longint):Integer;
{Binary search method}
var j:Integer;
begin
repeat
j:=(j1+j2) div 2;
if A=Sco[j] then begin Bfind:=-j; exit; end;
if A>Sco[j] then j2:=j-1 else j1:=j+1;
until j1>j2;
Bfind:=j1;
end;
procedure Sorting;
{Insert sorting Method}
var
i,j,j2:integer;
A:LongInt;
begin
Ns:=1;
for i:=2 to N do
begin
A:=Sco[i];
j2:=Bfind(1,Ns,A);
if j2>0 then
begin
for j:= Ns downto j2 do Sco[j+1]:=Sco[j];
Inc(Ns);
Sco[j2]:=A;
end;
end;
end;
var i,Sq:Integer;
begin
{ Read all Sco from keyboard }
Write('The Number of students:'); readln(N);
Writeln('Please enter all Sco:');
for i:=1 to N do read(Sco[i]); readln;
{Sorts all Sco}
Sorting;
{Inquiring}
Repeat
Write('The inquired score: (-1=Exit) '); readln(Sq);
if Sq<0 then exit;
writeln('Your sequence is:', abs(Bfind(1,Ns,Sq)));
until false;
end.
2015年01月15日 14点01分
1
网友提供了程序(略)。本人认为不够优化,给出优化后的程序。
该程序采用了以下方案:
1) 采用插入排序法对成绩表进行排序,去除重复项;采用对分搜索确定插入位置,效率高;
2) 可多次进行查询,查询采用对分搜索,效率高。被查询值可以是不在成绩表中的数值。
var
Sco:array[1..1000] of longint;
N,Ns:integer;
Function Bfind(j1,j2:Integer; A:Longint):Integer;
{Binary search method}
var j:Integer;
begin
repeat
j:=(j1+j2) div 2;
if A=Sco[j] then begin Bfind:=-j; exit; end;
if A>Sco[j] then j2:=j-1 else j1:=j+1;
until j1>j2;
Bfind:=j1;
end;
procedure Sorting;
{Insert sorting Method}
var
i,j,j2:integer;
A:LongInt;
begin
Ns:=1;
for i:=2 to N do
begin
A:=Sco[i];
j2:=Bfind(1,Ns,A);
if j2>0 then
begin
for j:= Ns downto j2 do Sco[j+1]:=Sco[j];
Inc(Ns);
Sco[j2]:=A;
end;
end;
end;
var i,Sq:Integer;
begin
{ Read all Sco from keyboard }
Write('The Number of students:'); readln(N);
Writeln('Please enter all Sco:');
for i:=1 to N do read(Sco[i]); readln;
{Sorts all Sco}
Sorting;
{Inquiring}
Repeat
Write('The inquired score: (-1=Exit) '); readln(Sq);
if Sq<0 then exit;
writeln('Your sequence is:', abs(Bfind(1,Ns,Sq)));
until false;
end.
