Hãy nhập câu hỏi của bạn vào đây, nếu là tài khoản VIP, bạn sẽ được ưu tiên trả lời.
Để chứng minh tính đúng đắn của thuật toán sắp xếp chèn với các lệnh thay đổi trên, ta cần chứng minh hai điều kiện sau đây:
Điều kiện ban đầu (trước khi bắt đầu vòng lặp): Sau khi thực hiện lệnh j = 1, giá trị của j đang là 1, và dãy con A[0] chỉ gồm một phần tử là A[0] (vì j-1 là 0). Do đó, dãy con này đã được sắp xếp đúng.
Điều kiện duy trì (trong quá trình vòng lặp): Trong mỗi vòng lặp của while, nếu A[j] < A[j-1], ta hoán đổi giá trị của A[j] và A[j-1] bằng lệnh Đổi chỗ A[j] và A[j-1]. Sau đó, ta giảm giá trị của j đi 1 đơn vị bằng lệnh j = j - 1. Lúc này, giá trị của A[j] là giá trị của A[j-1] trước khi hoán đổi, và giá trị của A[j-1] là giá trị của A[j] trước khi hoán đổi. Điều này đồng nghĩa với việc dãy con A[0], A[1], ..., A[j-1] đã được sắp xếp đúng sau mỗi vòng lặp.
Vậy nên, dãy con A[0], A[1], ..., A[j-1] luôn được sắp xếp đúng sau mỗi vòng lặp của while, và dãy con này sẽ không bị thay đổi giá trị trong quá trình hoán đổi. Do đó, tính đúng đắn của thuật toán sắp xếp chèn vẫn được duy trì sau khi thay toàn bộ phần chèn A[i] vào vị trí đúng của dãy con A[0], A[1], ..., A[i-1] bằng các lệnh trên.
Nếu A là một ma trận kích thước m x n, đoạn chương trình trên sẽ in ra giá trị của từng phần tử trong ma trận A, mỗi dòng một.
Cụ thể, với mỗi giá trị của i trong khoảng từ 0 đến m - 1, vòng lặp đầu tiên sẽ lặp qua từng phần tử trong hàng thứ i của ma trận A. Với mỗi giá trị của j trong khoảng từ 0 đến n-1, vòng lặp thứ hai sẽ in ra giá trị của phần tử tại vị trí (i,j) trong ma trận A bằng lệnh print(A[i][j],end=" "), kết thúc bằng một khoảng trắng.
Sau khi in hết các phần tử trong hàng thứ i, lệnh print() trong vòng lặp đầu tiên sẽ xuống dòng, chuyển sang in hàng tiếp theo của ma trận A. Như vậy, tổng hợp lại, đoạn chương trình sẽ in ra ma trận A dưới dạng bảng trên màn hình.
Công việc của hàm là thực hiện sắp xếp.
Độ phức tạp của thuật toán là O(n2)
#include <bits/stdc++.h>
using namespace std;
long long a[20],b[20],c[20],i,n;
int main()
{
cin>>n;
srand(time(NULL));
for (i=1; i<=n; i++)
a[i]=rand();
srand(time(NULL));
for (i=1; i<=n; i++)
b[i]=rand();
for (i=1; i<=n; i++)
c[i]=abs(a[i]-b[i]);
for (i=1; i<=n; i++) cout<<a[i]<<" "; cout<<endl;
for (i=1; i<=n; i++) cout<<b[i]<<" "; cout<<endl;
for (i=1; i<=n; i++) cout<<c[i]<<" "; cout<<endl;
return 0;
}
Độ phức tạp của thuật toán sắp xếp nổi bọt là O(n2)
T = O(n) + O(n2) = O(n2)
Bài 1:
uses crt;
var n,kt,d:integer;
st:string;
begin
clrscr;
write('Nhap bien so xe:'); readln(n);
str(n,st);
d:=length(st);
kt:=0;
if (st[d-1]='6') and (st[d]='8') then kt:=1;
if kt=0 then writeln('Day khong la bien so dep')
else writeln('Day la bien so xe dep');
readln;
end.
Bài 2:
uses crt;
var a,b,c:array[1..100]of integer;
n,i,min,x,t,dem,j,dem1,kt,max,min1,y,kt1:integer;
begin
clrscr;
write('Nhap n='); readln(n);
for i:=1 to n do
begin
write('A[',i,']='); readln(a[i]);
end;
writeln('Mang vua nhap la: ');
for i:=1 to n do
write(a[i]:4);
writeln;
min:=a[1];
for i:=1 to n do
if min>a[i] then min:=a[i];
writeln('Phan tu nho nhat trong mang la: ',min);
write('Nhap i='); readln(y);
for i:=1 to n do
if y=i then
begin
t:=0;
dem:=0;
for j:=1 to a[i] do
if a[i] mod j=0 then
begin
t:=t+j;
dem:=dem+1;
b[dem]:=j;
end;
end;
writeln('Cac uoc cua phan tu a[',y,'] trong mang la: ');
for i:=1 to dem do
write(b[i]:4);
writeln;
writeln('Tong cac uoc cua phan tu a[',y,'] trong mang la: ',t);
dem1:=0;
for i:=1 to n do
if a[i]>1 then
begin
kt:=0;
for j:=2 to a[i]-1 do
if a[i] mod j=0 then kt:=1;
if kt=0 then
begin
inc(dem1);
c[dem1]:=a[i];
end;
end;
max:=c[1];
min1:=c[1];
for i:=1 to dem1 do
begin
if max<c[i] then max:=c[i];
if min1>c[i] then min1:=c[i];
end;
writeln('Tong cua so nguyen to lon nhat va so nguyen to nho nhat trong mang la: ',max+min1);
write('Nhap x='); readln(x);
kt1:=0;
for i:=1 to n do
begin
if i<x then
begin
for j:=i to x do
if a[j]<>a[x-j+1] then kt1:=1;
end;
end;
if kt1=0 then writeln('Khong co ',x,' so doi xung dung canh nhau')
else writeln('Co ',x,' so doi xung dung canh nhau');
readln;
end.
#include <iostream>
#include <fstream>
using namespace std;
long int x[4],n,a[5001],kt[5001],ktvt[5001],MAXtong,dem=0;
int TRY(int i)
{
for(int j=x[i-1]+1;j<=n;j++)
if(kt[a[j]]==0)
{
x[i]=j;
kt[a[j]]=1;
if(i==3)
{
if(a[x[3]]==(float)(a[x[2]]+a[x[1]])/2||a[x[2]]==(float)(a[x[3]]+a[x[1]])/2||a[x[1]]==(float)(a[x[2]]+a[x[3]])/2)
{
dem++;
if(a[x[1]]+a[x[2]]+a[x[3]]>MAXtong)
{
MAXtong=a[x[1]]+a[x[2]]+a[x[3]];
}
}
}
else
TRY(i+1);
kt[a[j]]=0;
}
}
int main()
{
ifstream f("boba.inp");
f>>n;
for(int i=1;i<=n;i++)
{
f>>a[i];
}
x[0]=0;
MAXtong=-1000000000;
fill_n(kt,1001,0);
TRY(1);
cout<<dem<<endl;
if(dem>0)
{
cout<<MAXtong;
}
return 0;
}
Mình mới đạt tới trình độ quy hoạch động nên bạn thông cảm
Xin lỗi bạn, mình không hỗ trợ C. mình chỉ biết pascal thôi
const fi='tamhop.inp';
fo='tamhop.out';
var f1,f2:text;
a:array[1..100]of integer;
n,i,j,k,dem,max,t:integer;
begin
assign(f1,fi); reset(f1);
assign(f2,fo); rewrite(f2);
readln(f1,n);
for i:=1 to n do
read(f1,a[i]);
{--------------------------------xu-ly--------------------------------}
dem:=0; max:=0;
for i:=1 to n-2 do
begin
for j:=i+1 to n-1 do
begin
for k:=j+1 to n do
begin
if (a[i]=(a[j]+a[k])/2) or (a[j]=(a[i]+a[k])/2) or (a[k]=(a[i]+a[j])/2) then
begin
inc(dem);
t:=a[i]+a[j]+a[k];
if max<=t then max:=t;
end;
end;
end;
end;
writeln(f2,dem);
writeln(f2,max);
close(f1);
close(f2);
end.
