Bài toán: Tích lớn nhất trong 3 số

In

Thứ năm, 21 Tháng 7 2011 22:17

tinhoche11_04

Bài toán: Tích lớn nhất trong 3 số                              Mã file: MULMAX3

Cho một dãy số nguyên a1, a2,…, an.

Yêu cầu: Hãy chọn ra 3 số trong dãy trên sao cho tích của chúng là lớn nhất.

 

Dữ liệu vào từ file ‘MULMAX3.INP’

Kết quả ghi vào file ‘MULMAX3.OUT’ ghi tích lớn nhất tìm được.

Giới hạn kỹ thuật:

Ví dụ:

MULMAX3.INP

MULMAX3.OUT

6

7 -2 4 -1 6 5

210

Lời giải tham khảo:

Lời giải 1:

const fi='MULMAX3.inp';
      fo='MULMAX3.out';
var f:text;
    a:array[1..10000] of int64;
    n,max:int64;
procedure nhap;
      var i:longint;
        begin
                assign(f,fi);
                reset(f);
                readln(f,n);
                for i:=1 to n do
                    readln(f,a[i]);
                close(f);
        end;

procedure qsort(l,r:integer);
        var i,j,x,y: integer;
begin

                i:=l;
                j:=r;
        x:=a[(l+r) div 2];
        repeat
                while a[i]<x do i:=i+1;
                while a[j]>x do j:=j-1;
                if i<=j then
                  begin
                        y:=a[i];
                        a[i]:=a[j];
                        a[j]:=y;
                        i:=i+1;
                        j:=j-1;
                  end;
        until i>j;
        if l<j then qsort(l,j);
        if i<r then qsort(i,r);

end;
{chua toi uu, dang thu}
procedure xuli;
      var   kq:qword;
begin
          qsort(1,n);
          max:=a[n]*a[n-1]*a[n-2];
          kq:=a[1]*a[2]*a[n];
          if kq>max then max:=kq;

end;

procedure xuat;

begin
        assign(f,fo);
        rewrite(f);
        write(f,max);
        close(f);
end;

{chuong trinh chinh}
begin
        nhap;
        xuli;
        xuat;
end.

Lời giải 2:

const fi='mulmax3.inp';
      fo='mulmax3.out';
var a:array[1..1000000] of longint;
    n:longint;
    kq:qword;
    f:text;
procedure docfile;
var i:integer;
begin
    assign(f,fi);reset(f);
    readln(f,n);
    for i:=1 to n do
        read(f,a[i]);
    close(f);
end;

procedure ghifile;
begin
    assign(f,fo);rewrite(f);
    writeln(f,kq);
    close(f);
end;

procedure trao(var x,y:longint);
var tmp:longint;
begin
    tmp:=x;
    x:=y;
    y:=tmp;
end;

procedure quicksort(d,c:longint);
var i,j,x:longint;
begin
    i:=d;
    j:=c;
    x:=a[(i+j) div 2];
    repeat
        while a[i]<x do inc(i);
        while a[j]>x do dec(j);
        if i<=j then
            begin
                trao(a[i],a[j]);
                inc(i);dec(j);
            end;
    until i>j;
    if i<c then quicksort(i,c);
    if d<j then quicksort(d,j);
end;

procedure xuly;
begin
    quicksort(1,n);
    kq:=int64(a[n])*int64(a[n-1])*int64(a[n-2]);
    if kq<int64(a[1])*int64(a[2])*int64(a[n]) then
        kq:=int64(a[1])*int64(a[2])*int64(a[n]);
end;

begin
    docfile;
    xuly;
    ghifile;
end.

(Chương trình tập huấn kỹ năng lập trình và công tác bồi dưỡng HSG dành cho GV THCS - hè 2011)