aj có đề pascal nào ko hĩu thì post lên !!!

[ThànhAnh]

Lâu ko vào forum,thấy cái topic này shock à nha.May quá,đang có bài này ko hiểu,nhờ bạn làm giùm luôn.
Cho một dãy số 123456789 và một số n.Hãy tìm cách thêm các dấu '+' và '-' vào dãy số để được kết quả là số n
Ví dụ
n=45
1+2+3+4+5+6+7+8+9
n=171
12+34+56+78-9
Nếu có nhiều kết quả thì in ra tất cả các kết quả

bài giải nè:
Const t1 = 'chenxau.inp';
t2 = 'chenxau.out';
dau: array[1..3] of String[1]= ('', '-', '+');
s:array[1..9] of char=('1','2','3','4','5','6','7','8','9');
Var d:array[1..9] of String[1];
m:longInt;
fi,fo:text;
k:integer;
found:boolean;
procedure mo;
begin
assign(fi,t1);reset(fi);
assign(fo,t2);rewrite(fo);
end;
Procedure Nhap;
Begin
Read(fi,m);
found:=false;
end;
Function tinh(s:string):longint;
Var i,t:longint;
code:integer;
Begin
i:=length(s);
While not(s[i] in ['-','+']) and (i>0) do dec(i);
val(copy(s,i+1,length(s)-i),t,code);
If i=0 then begin tinh:=t; exit; end
else
begin
delete(s,i,length(s)-i+1);
If s[i]='+' then tinh:=t+tinh(s);
If s[i]='-' then tinh:=tinh(s)-t;
end;
End;
Procedure Xuat(i:integer);
Var st:string; j:integer;
Begin
st:='';
For j:=1 to i do st:=st+d[j]+s[j];
If Tinh(st) = m then begin writeln(fo,st); found:=true; end;
End;
Procedure Try(i:integer);
Var j:integer;
Begin
for j:=1 to 3 do
begin
d[i]:=dau[j];
If i<9 then try(i+1);
If i=9 then Xuat(i);
end;
End;
procedure dong;
begin
close(fi);close(fo);
end;
BEGIN
mo;
nhap;
for k:=1 to 2 do
begin
d[1]:=dau[k];
Try(2);
end;
If not found then write(fo,'khong co ngiem');
END.

[boysitinh_vl]

Ngay cả tên nick của bạn cũng đã thể hiện rồi,''vl'' là viết tắt của từ gì,có lẽ chúng tôi đều hiểu,chỉ là ngại ko nói ra.

"vl"-> vĩnh long pa ơi!!! tôi ở vĩnh long
tại hồi nãy bận đi học nên làm bài ko kỉ nên mới dài zậy thui chứ nó ngắn lắm!!! bài hồi nãy ko sai chỉ tội quá dài và hơi khó hĩu
cách khác ngắn hơn nè :
xét ">" liên tiếp , vd: >>>><<<> ->max> =4, vtmax=5
xét "<" liên tiếp , vd: >>>><<<> ->max< =3, vtmax=8
=> số max pé nhất là 4+1, tức là max nào lớn thì đó là số lớn nhất pé nhất mình cần tìm. vtmax là vị trí chèn số max vào !!!
công việc còn lại là 2 cái for
1. for vtmax->1
2. for vtmax+1->n+1
rồi xét nếu ko bít thì cứ kêu mình post lên lun chứ bây giờ đang bận
gợi ý chia làm 2 mãng sẽ làm rất nhanh mãng : so và dau
dau[i-1]->so[i]
khj xuất sẽ là: so[i],dau[i]

[phuclun]

@Mr_invincible:ko ,tui muốn hỏi về thuật toán của bàì 2,ko phải bài 1
@boysitinh_vl:uhm,tui sai.Tui xin lỗi về vụ đó.Bốc đồng,có lẽ là vậy,1 đức tính ko nên có của người làm Tin-->có mình tui hiểu bậy-->Quê.

[phuclun]

bài của m2mpro thì tui nghĩ thế này
Đầu tiên phải kt xem số a[1] là số nào{điều này chắc các bạn làm được},sau đó nhờ nó ta dùng thuật toán sau
for i:=2 to n do
Nếu gặp dấu > cứ thoải mái inc(a[i]),nếu gặp dấu giảm thì kt xem đằng sau nó có bao nhiêu dấu giảm,nếu số dấu giảm{s} > a[i] thì sẽ a[i]:=s-a[i]+1{để đến sau dấu giảm cuối cùng a[j]=1},còn nếu s<a[i] thì a[i+1]:=s ,mục đích của 2 việc gán này là để đến sau dấu giảm cuối cùng a[j]=1,sau khi gán thì tất cả các số sau dấu giảm đều phải giảm 1,trong lúc làm như vậy thì kết hợp kiểm tra tìm biến max.
Bài này theo mình sẽ dùng for trong đó có while do,độ phức tạp ko quá O(2n)-->chạy khá nhanh.
Phát biểu linh tinh,có gì sai xin góp ý.

[boysitinh_vl]

bài của m2mpro thì tui nghĩ thế này
Đầu tiên phải kt xem số a[1] là số nào{điều này chắc các bạn làm được},sau đó nhờ nó ta dùng thuật toán sau
for i:=2 to n do
Nếu gặp dấu > cứ thoải mái inc(a[i]),nếu gặp dấu giảm thì kt xem đằng sau nó có bao nhiêu dấu giảm,nếu số dấu giảm{s} > a[i] thì sẽ a[i]:=s-a[i]+1{để đến sau dấu giảm cuối cùng a[j]=1},còn nếu s<a[i] thì a[i+1]:=s+1 ,mục đích của 2 việc gán này là để đến sau dấu giảm cuối cùng a[j]=1,sau khi gán thì tất cả các số sau dấu giảm đều phải giảm 1,trong lúc làm như vậy thì kết hợp kiểm tra tìm biến max.
Bài này theo mình sẽ dùng for trong đó có while do,độ phức tạp ko quá O(2n)-->chạy khá nhanh.
Phát biểu linh tinh,có gì sai xin góp ý.

làm cách bạn coi chừng chết đó
làm sao bít được đằng trước có bao nhiu dấu ">" bạn chỉ đi, đó là điều quan trọng trừ khi làm trước thấy không được rồi quay lại mà như zậy phức tap >O(2n) nếu rơi vào trường hợp hi hữu là ">" quá nhìu quay lại sẽ mất khoảng t/g rất lâu.
vd: 1>2>3>4>3>2>1>0>-1>...>-800<...>
dù sao cám ơn bạn đã đóng góp. Bài của mình độ phức tap O(2n) đó !!! Cách của bạn thì rút ngắn cái đầu nhưng cái sau ko có bọc lót được nên kết quả ko ổn định! nếu bít được đằng sau có bao nhiu dấu ">" hoặc "<" thì bài của mình độ phức tạp cũng nhỏ hơn O(2n) thuj
Nhưng đề bài chỉ yêu cầu mảng có kích thước 1000 àh làm sao mà không ra nhanh !!!

[bete]

Thân gửi bạn boysitinh

bài hồi nãy ko sai chỉ tội quá dài và hơi khó hĩu; cách khác ngắn hơn nè :
xét ">" liên tiếp , vd: >>>><<<> ->max> =4, vtmax=5
xét "<" liên tiếp , vd: >>>><<<> ->max< =3, vtmax=8
=> số max pé nhất là 4+1, tức là max nào lớn thì đó là số lớn nhất pé nhất mình cần tìm. vtmax là vị trí chèn số max vào !!!

=> cách giải đầu tiên của bạn tui xin có chút thắc mắc:

cho tất cả mang=mang2
if mang[1]='>' then
begin
xét for từ i:=1 cho đến n
chừng nào mang[i]<>mang[i] thì

=> mình so sánh mang[i] với mang[i] thì là kết quả luôn là true ????

Còn nếu ý của bạn là mang[i]<>mang2[i]
thì vì mình đã cho tất cả mang=mang2 nên kết quả cũng luôn là true ???

Còn cách giải mới của bạn thì tui cũng xin có chút thắc mắc:

Giả sử mình có:
<<<><<<>>>>

Nếu tui không lầm thì cách giải mới của bạn sẽ là như sau:
xét ">" liên tiếp -> max> =4, vtmax=12
xét "<" liên tiếp -> max< =3, vtmax=4 hoặc 8
=> số max nhỏ nhứt là 4+1=5, tức là max nào lớn thì đó là số lớn nhất nhỏ nhứt mình cần tìm. vtmax là vị trí chèn số max vào !!!

Nhưng tui lại thấy số max nhỏ nhứt phải là 6:
1<2<3<4>3<4<5<6>5>4>3>2

=> không biết tui có hiểu sai thuật toán của bạn hay không ?

Tui xin giải thử như sau:
<<<>>>>><<<
=> bắt đầu từ 1:
1<2<3<4>3>2>1>0>-1<0<1<2
=> mình thấy số min là -1 => phải hiệu chỉnh: tăng mỗi số lên 2 (để số min là 1):
3<4<5<6>5>4>3>2>1<2<3

(>>>><<<
=> 1>0>-1>-2>-3<-2<-1<0
=> số min là -3 => phải tăng mỗi số lên 4
=> 5>4>3>2>1<2<3<4)

=> quét mảng 2 lần
=> độ phức tạp là O(n) (chớ không phải là O(2n); nếu viết O(2n) thì hóa ra O(n)=O(1n) có nghĩa là chỉ quét mảng có 1 lần thôi hay sao ?)

(hiểu biết nông cạn; có gì sai sót mong được góp ý; xin cám ơn)

-thân

[mr_invincible]

Ah nghe cái topic này ghê gớm quá. Hỏi thử một bài vừa phải nhé:
Cho dãy số A[1]...A[n]. Tìm lần lượt các số nhỏ nhất trong các số:
A[1]...A[k]
A[2]...A[k+1]
...
A[n-k+1]...A[n]
Giới hạn: Độ phức tạp O(n)
VD:
Input:
3 5 2 4 1 3
k=3
Output:
2 2 1 1

Hình như anh bete quên đọc bài của em

[bete]

Cho số N (N<=10^9). Tìm chữ số tận cùng khác 0 của n!

Tui nghĩ như vầy:

Giả sử n=123456785
Đặt f(n): hàm trả về chữ số tận cùng khác 0 của n giai thừa
g(n): hàm trả về chữ số tận cùng khác 0 của n

Một vài nhận xét:

1) có đúng 12345678 số tận cùng là [0,1,...,9] trong khoảng 1->123456780
Có đúng 1 số tận cùng là [1,...,5] trong khoảng 123456781->123456785
=> có đúng (12345678+1) số tận cùng là [1,...,5] trong khoảng 1->123456785
Có đúng 12345678 số tận cùng là [0,6,7,...,9] trong khoảng 1->123456785

2) Xét hàm g (tìm chữ số tận cùng -- có thể bằng 0):
g(8^1)=8; g(8^2)=4; g(8^3)=2; g(8^4)=6; g(8^5)=8; g(8^6)=4; ...
=> "chu kỳ" của 8 là 4: g(8^k) = g(8^[((k+3) mod 4) + 1])
(chữ số cuối cùng của 8^k sẽ là chữ số cuối cùng của 8^[((k+3) mod 4)+1])

=> tương tự mình có thể tìm "chu kỳ" của mọi chữ số 0->9
("chu kỳ" của 1 chữ số nói chung không quá 5)

3) Xét hàm g (tìm chữ số tận cùng -- có thể bằng 0):
Nếu số nguyên dương m tận cùng là 8 thì g(m^k) = g(8^k)
=> g(m) = g(8^[((k+3) mod 4) + 1])
(nếu m tận cùng là d thì g(m^k) = g(d^[((k+p-1) mod p) + 1]); với p là "chu kỳ" của d)

4) Có đúng (12345678+1) số tận cùng là [1,...,5] trong khoảng 1->123456785
Có đúng 12345678 số tận cùng là [0,6,7,...,9] trong khoảng 1->123456785

Gọi S0 là các số trong khoảng 1->123456785! tận cùng là 0: có 12345678 số trong S0. Gọi T0 là tích của 12345678 số thuộc S0: g(T0)=g(0^12345678)=g(0^1) (vì "chu kỳ" của 0 là 1)

Gọi S1 là các số trong khoảng 1->123456785! tận cùng là 1: có 12345679 số trong S1. Gọi T1 là tích của 12345679 số thuộc S1: g(T1)=g(1^123456789)=g(1^1) (vì "chu kỳ" của 1 là 1)

Gọi S2 là các số trong khoảng 1->123456785! tận cùng là 2: có 12345679 số trong S2. Gọi T2 là tích của 12345679 số thuộc S2: g(T2)=g(2^123456789)=g(2^[((123456789+3) mod 4)+1) (vì "chu kỳ" của 2 là 4)
g(T2)=g(2^(0+1))=g(2)=2

............

5) Xét hàm f (tìm chữ số tận cùng khác 0 của n giai thừa)
Bỏ qua các Tk thỏa g(Tk) là 0; chỉ xét các Tk thỏa g(Tk) khác 0 và khác 1
Đặt m = tích các g(Tk) với g(Tk) khác 0 và khác 1;
f(123456785!) = f(T0*T1*...*T9) = f(m)
(thay vì phải làm n! phép nhân thì mình chỉ cần làm không quá 50 phép nhân)

(hiểu biết nông cạn; có gì sai sót mong được góp ý; xin cám ơn)

-thân

[boysitinh_vl]

Thân gửi bạn boysitinh

Còn cách giải mới của bạn thì tui cũng xin có chút thắc mắc:

Giả sử mình có:
<<<><<<>>>>

Nếu tui không lầm thì cách giải mới của bạn sẽ là như sau:
xét ">" liên tiếp -> max> =4, vtmax=12
xét "<" liên tiếp -> max< =3, vtmax=4 hoặc 8
=> số max nhỏ nhứt là 4+1=5, tức là max nào lớn thì đó là số lớn nhất nhỏ nhứt mình cần tìm. vtmax là vị trí chèn số max vào !!!

Nhưng tui lại thấy số max nhỏ nhứt phải là 6:
1<2<3<4>3<4<5<6>5>4>3>2

=> không biết tui có hiểu sai thuật toán của bạn hay không ?

hỉu sai rồi chứ còn hay không cái gì!!! tui nói tại điểm đó là điền vào max còn max thực sự trong lúc điền phải xét chứ bạn !!! max điền vào chổ đó chắc chắn sẽ làm cho max thực sự là pé nhất. Không tin bạn cứ test. mà đề bài yêu cầu giới hạn có 1000 phần tử làm sao mà không được!
còn bạn nói O(2n) cái đó thì mình chịu chã bít gì thấy người ta nói thì nói đại
tưởng xét 2 lần cái mảng thì O(2n). xin lỗi hỉu bít nông cạn. hjhj
thân

[bete]

Thân gửi bạn boysitinh,

còn max thực sự trong lúc điền phải xét chứ

=> tui không hiểu cho lắm
Bạn đã viết

xét ">" liên tiếp , vd: >>>><<<> ->max> =4, vtmax=5
xét "<" liên tiếp , vd: >>>><<<> ->max< =3, vtmax=8
=> số max pé nhất là 4+1, tức là max nào lớn thì đó là số lớn nhất pé nhất mình cần tìm.

=> như vậy nếu mình có

xét ">" liên tiếp -> max> =4, vtmax=12
xét "<" liên tiếp -> max< =3, vtmax=4 hoặc 8

=> thì có phải mình cần điền 5 vô vị trí 12 hay không ?

Để cho rõ: bạn có thể viết ra cách giải cho trường hợp "<<<><<<>>>>" được hay không (xin cám ơn trước)

-thân