Các bài toán đặc biệt về mảng một chiều

Bài 5:Viết chương trình nhập vào từ bàn phím mảng một chiều A gồm M phần tử, mảng một chiều B gồm N phần tử, sắp xếp 2 dãy A và B tăng dần sau đó trộn 2 dãy thành dãy C sao cho dãy C cũng là dãy đã được sắp xếp tăng dần. In mảng A, B, C ra màn hình.

Code:

uses crt;
var a,b,c:array[1..100] of integer;
    i,n,j,k,m,d,e,f:integer;
procedure dc(var a,b:integer);
var t:integer;
begin
t:=a;
a:=b;
b:=t;
end;
{-}
begin
clrscr;
write('nhap so phan tu cua mang 1 va 2:');readln(n,m);
for i:=1 to n do
    begin
        write('a[',i,']:');readln(a[i]);
    end;
for i:=1 to m do
    begin
        write('b[',i,']:');readln(b[i]);
    end;
{mang a va mang b tu xuat ra nhe ban}
c:=a;
d:=m+n;
for i:=n+1 to d do
    begin
        e:=e+1;
        c[i]:=b[e];
    end;
for i:=1 to d-1 do
for j:=i+1 to d do
if c[i]>c[j] then dc(c[i],c[j]);
for i:=1 to d do write(c[i]:3);
readln;
end.

Bài 3:Bài tập 3: Viết chương trình nhập vào một dãy số nguyên có n phần tử.
a. Đưa những phần tử lẻ ra đầu danh sách, những phần tử chẵn về cuối danh sách và in kết quả ra màn hình.
b. Sắp xếp các phần tử lẻ đầu danh sách theo thứ tứ tăng dần, sắp xếp các phần tử chẵn cuối danh sách theo thứ tự giảm dần. In danh sách ra màn hình.

Code:

uses crt;
var a:array[1..100] of integer;
    i,n,j,k,b,c:integer;
procedure dc(var a,b:integer);
var t:integer;
begin
t:=a;
a:=b;
b:=t;
end;
{-}
begin
clrscr;
write('nhap so phan tu cua day:');readln(n);
for i:=1 to n do
    begin
         write('a[',i,']:');readln(a[i]);
    end;
for i:=1 to n-1 do
for j:=i+1 to n do
if (a[i] mod 2=0) and (a[j] mod 2=1) then dc(a[i],a[j]);
writeln('mang sau khi sap xep giai doan 1;');
for i:=1 to n do write(a[i]:3);
for i:=1 to n-1 do
for j:=i+1 to n do
if (a[i]<a[j]) and (a[i] mod 2=1) and (a[j] mod 2=1) then
dc(a[i],a[j]);
for i:=1 to n-1 do
for j:=i+1 to n do
if (a[i]>a[j]) and (a[i] mod 2=0) and (a[j] mod 2=0) then
dc(a[i],a[j]);
writeln;
writeln('mang sau khi sap xep giai doan 2:');
for i:=1 to n do write(a[i]:3);
readln;
end.

Bài giải:
uses crt;
var a,b: array[1..100] of byte;
n,i,j,min,d: byte;
procedure doi(var a,b:byte);
begin
a:= a+b;
b:= a-b;
a:= a-b;
end;
begin
clrscr;
write('Nhap so phan tu: '); readln(n);
j:= 0;
for i:= 1 to n do
begin
if j<3 then inc(j) else j:= 1;
a[i]:= j;
write(a[i]:2);
end;
writeln;
for i:= 1 to n do b[i]:= a[i];
for i:= 1 to n-1 do
for j:= i+1 to n do
if b[i]>b[j] then
doi(b[i],b[j]);
min:= 0;
for i:=1 to n do if a[i]<>b[i] then inc(min);
min:= min div 2 + min mod 2;
writeln('So lan doi cho it nhat: ',min);
if min>0 then
begin
writeln('Cac thao tac doi cho: ');
i:= 0;
repeat
repeat inc(i) until a[i]<>b[i];
j:= i;
repeat inc(j) until a[j]=b[i];
write(' (',i:2,';',j:2,') ');
doi(a[i],a[j]);
inc(d);
until d=min;
end;
readln
end.

Viết chương trình tạo dãy chỉ gồm các phần tử 1; 2; 3 với số phần tử được nhập từ bàn phím. In ra màn hình số lần đổi chỗ ít nhất để dãy trên là dãy không giảm. Đồng thời in ra từng thao tác thực hiện (in ra thứ tự của các phần tử trong thao tác đổi chỗ).
Vd: Với số phần tử là 4 ->Dãy là 1; 2; 3; 1
=> Số lần đổi chỗ ít nhất: 2
Các thao tác đổi chỗ: (2;4) (3;4)

phong đã viết:

Hình như thiếu thuật toán sắp xếp.

Thuật toán sắp xếp đã được đề cập ở bài 15 (trong post "Các bài toán về mảng một chiều") rồi thưa thầy

Hình như thiếu thuật toán sắp xếp.
Các bài này hay hay anh em giải chơi nha.
Thuật toán sắp xếp và một số bài tập áp dụng thuật toán sắp xếp:
Bài tập 1: (Bài toán cơ bản)
Viết chương trình vào từ bàn phím số nguyên N và mảng A gồm N phần tử. In ra màn hình mảng A sau khi đã sắp xếp các phần tử theo thứ tự tăng dần.
Bài tập 2: Viết chương trình vào từ bàn phím số nguyên N và mảng A gồm N phần tử. In ra màn hình mảng A sau khi đã sắp xếp các phần tử theo thứ tự giảm dần.
Bài tập 3: Viết chương trình nhập vào một dãy số nguyên có n phần tử.
a. Đưa những phần tử lẻ ra đầu danh sách, những phần tử chẵn về cuối danh sách và in kết quả ra màn hình.
b. Sắp xếp các phần tử lẻ đầu danh sách theo thứ tứ tăng dần, sắp xếp các phần tử chẵn cuối danh sách theo thứ tự giảm dần. In danh sách ra màn hình.
Bài tập 4: Viết chương trình nhập vào từ bàn phím mảng A gồm N phần tử là số nguyên gồm 3 loại số : Loại 1 : các số vừa chia hết cho 3 vừa lẻ, loại 3 : các số vừa chia hết cho 3 vừa chẵn, loại 2 : các số còn lại . Yêu cầu hãy xếp các số loại 1 lên đầu dãy , các số loại 3 xuống cuối dãy , các số loại 2 ở giữa dãy . Trước hết xếp gọn hết các số loại 1 , sau đó xếp đồng thời các số loại 2 và 3. Đưa ra màn hình dãy đã được sắp xếp.

Dữ liệu vào Dữ liệu ra
N=8
88 29 81 12 42 35 62 83 88 29 81 12 42 35 62 83
81 29 88 62 83 35 12 42
Bài tập 5: Viết chương trình nhập vào từ bàn phím mảng một chiều A gồm M phần tử, mảng một chiều B gồm N phần tử, sắp xếp 2 dãy A và B tăng dần sau đó trộn 2 dãy thành dãy C sao cho dãy C cũng là dãy đã được sắp xếp tăng dần. In mảng A, B, C ra màn hình.

Bài 1: Cho 2 dãy số thực a1,a2,a3,…,an (1) ; b1,b2,b3,…,bm (2). Dãy (1) được gọi là dãy con của dãy 2 nếu bỏ đi k phần tử (k>=0) trong (2) thì có (1). Chẳng hạn: dãy 1,3,5 là dãy con của dãy 0,1,2,1,4,3,5,7. Hãy nhập vào 2 dãy và cho biết dãy (1) có phải là dãy con của dãy (2) hay không.

Bài 2: “Dãy đoạn con” tương tự dãy con nhưng các phần tử liên tiếp. Chẳng hạn: dãy 1,2,1 là dãy đoạn con của dãy 0,1,2,1,4,5,6,3. Còn dãy 1,4,6 không là dãy đoạn con của nó. Hãy nhập vào 2 dãy và cho biết dãy (1) có phải là dãy đoạn con không.

Bài 3: Dãy được gọi là đối xứng nếu viết các phần tử của nó theo thứ tự ngược lại thì vẫn được chính nó. Dãy được gọi là khả đối xứng nếu đổi chổ các phần tử của nó thì được dãy đối xứng. Cho một dãy số nguyên, kiểm tra xem nó có khả năng đối xứng hay không? Nếu có thì biến đổi nó để được một dãy đối xứng.

Bài 4: Dãy số tự nhiên a1;a2;…;ak được gọi là hạnh phúc thỏa mãn các điều kiện sau:
  +) Dãy trên là một dãy giảm dần.
  +) Với mọi i ai hoặc là số nguyên tố hoặc phải là ước của một trong các số a1;a2;…;ai.
Ví dụ: 8,7,5,4,3,2,1 là dãy số hạnh phúc ( với n=8 dãy số hạnh phúc có 7 phần tử).
Yêu cầu hãy viết chương trình nhập vào một số tự nhiên N từ bàn phím và in ra màn hình một dãy số hạnh phúc càng dài càng tốt với số hạng đàu tiên là N.

Bài 5: Trong một dãy số, các phần tử bằng nhau liên tiếp được gọ là 1 mặt bằng của dãy. Mặt bằng lớn nhất là mặt bằng của dãy có số phần tử nhiều nhất. Cho dãy số nguyên n. Tìm mặt bằng lớn nhất.

Bài 6: Ở một vương quốc nọ có một ông vua rất hung ác. Ông ta quyết định cho n người tự sát tập thể. Họ đứng thành một vòng tròn và người thứ m tự sát, tính thứ tự theo một chiều nào đó, chẳng hạn chiều kim đồng hồ. Khi một người ngã xuống thì vòng tròn thu hẹp lại và đếm thứ tự người còn lại bên cạnh để xác định người tự xác tiếp theo. Nhập 2 số tự nhiên n và m, liệt kê thứ tự từng người bị giêt.
VD: với n=9, m=5 thì thứ tự là: 5, 1, 7, 4, 3, 6, 9, 2, 8.