Giải thích giúp mình thuật toán của bài này cho minh với( khó quá)

vansonqtqb · 15/7/16

giải thích giúp mình thuật toán của bài này cho minh với( khó quá)
Cho một số nguyên dương N gồm có M chữ số. (1

Yêu cầu: Xóa đi K chữ số trong N để thu được số N’ sao cho N’ có giá trị nhỏ nhất.

(K <= M).

Dữ liệu vào: Cho trong file văn bản XOASO.INP có cấu trúc như sau:
Dòng 1: Ghi số hai số nguyên dương N K. Hai số được ghi cách nhau ít nhất một dấu cách.
Dữ liệu ra: Ghi ra file văn bản XOASO.OUT theo cấu trúc như sau:
Dòng 1: Ghi số N’ tìm được. (Vẫn giữ các chữ số 0 ở đầu số nếu có)
Ví dụ:

XOASO.INP XOASO.OUT XOASO.INP XOASO.OUT
123952 2 1232 95002 2 002

> const

fi='xoaso.in7';
fo='xoas

U7';
var f,g:text;
k,i,j,n,code,a,b:integer;
sok,s:string;
dd:integer;
begin
assign(f,fi);
assign(g,fo);
reset(f);
rewrite(g);
read(f,s);
for i:=length(s) downto 1 do if s=' ' then begin
sok:= copy(s,i+1,length(s)-i); break end;
val(sok,k,code);
writeln(k);
delete(s,pos(' ',s), length(s)-pos(' ',s)+1);
writeln(s);
for i:=1 to k do
begin
j:=1;
dd:=length(s);
while j<length(s) do
begin
val(s[j],a,code);
val(s[j+1],b,code);
if a>b then
begin
delete(s,j,1);
break
end
else inc(j);
end;
if j=dd then delete(s,dd,1);
end;
write(g,s);
close(f);
close(g);
end.

tengiday · 15/7/16

Reply: giải thích giúp mình thuật toán của bài này cho minh với( khó quá)

Dòng loop thực thi thuật toán là đây:

Mã:

for i := 1 to k do
   begin
      j := 1;
      dd := length(s);
      while j < length(s) do
         begin
            val(s[j], a, code);
            val(s[j + 1], b, code);
            if a > b then
               begin
                  delete(s, j, 1);
                  break
               end
                  else inc(j);
         end;
            if j = dd then delete(s, dd, 1);
   end;

Những đoạn codes khác là lấy input và in ra output.

Đơn giản nhất là bắt đầu thế này nhé: Cho 1 số nguyên dương N, làm sao xóa 1 chữ số sao cho số N còn lại là nhỏ nhất. (Thực hiện như thế K lần để giải bài này).

Bạn thử suy nghĩ 2 câu hỏi sau trước khi đọc xuống dưới:
- Khi có 1 chuỗi chữ số tăng dần, cần xóa chữ số nào để số còn lại là nhỏ nhất?
- Khi có 1 chuỗi chữ số giảm dần, cần xóa chữ số nào để số còn lại là nhỏ nhất?

Chúng ta đi từ trái sang phải của số nguyên dương N, nếu gặp 2 chữ số ab liên tục nhau với a > b thì xóa số a đi. Nếu ko có chữ số ab như vậy thì xóa chữ số cuối đi.

Ví dụ:
N = 123952
K = 2
- Xóa đi 1 chữ số của N = 123952:
ab = '12', Ko làm gì cả, N = 123952
ab = '23', Ko làm gì cả, N = 123952
ab = '39', Ko làm gì cả, N = 123952
ab = '95', Xóa số 9, N = 12352

- Xóa đi 1 chữ số của N = 12352:
ab = '12', Ko làm gì cả, N = 12352
ab = '23', Ko làm gì cả, N = 12352
ab = '35', Ko làm gì cả N = 12352
ab = '52', Xóa số 5, N = 1232

Như vậy là đã xóa đc 2 chữ số.
Kết quả 1232.

phamthanhnhan · 15/7/16

Reply: giải thích giúp mình thuật toán của bài này cho minh với( khó quá)

thuật toán của thớt trên hay nhỉ :gach:

VSupport · 15/7/16

tengiday thánh quá, ngưỡng mộ bạn thật :xinhqua:

tengiday · 16/7/16

VSupport:
tengiday thánh quá, ngưỡng mộ bạn thật

Cám ơn bạn, mình chỉ dịch giúp thuật toán của chủ topic thôi.

vansonqtqb · 16/7/16

trước hết mình cảm ơn các bạn đã giúp mình.
cảm ơn bạn tenjday.cũng nhờ bạn nói lại đoạn chương trình này cho mình với(thực sự mình chưa biết là nó dùng để làm j)
và tại sao k chữ số lại được tính trong đoạn này) thank
for i:=length(s) downto 1 do if s=' ' then begin
sok:= copy(s,i+1,length(s)-i); break end;
val(sok,k,code);
writeln(k);
delete(s,pos(' ',s), length(s)-pos(' ',s)+1);
writeln(s);

tengiday · 16/7/16

vansonqtqb:
trước hết mình cảm ơn các bạn đã giúp mình.
cảm ơn bạn tenjday.cũng nhờ bạn nói lại đoạn chương trình này cho mình với(thực sự mình chưa biết là nó dùng để làm j)
và tại sao k chữ số lại được tính trong đoạn này) thank

Mã:

[COLOR=#000000][FONT=Arial]for i:=length(s) downto 1 do if s[i]=' ' then begin[/FONT][/COLOR] [COLOR=#000000][FONT=Arial] sok:= copy(s,i+1,length(s)-i); break end;[/FONT][/COLOR] [COLOR=#000000][FONT=Arial]val(sok,k,code);[/FONT][/COLOR] [COLOR=#000000][FONT=Arial]writeln(k);[/FONT][/COLOR] [COLOR=#000000][FONT=Arial]delete(s,pos(' ',s), length(s)-pos(' ',s)+1);[/FONT][/COLOR] [COLOR=#000000][FONT=Arial]writeln(s); [/FONT][/COLOR]

Đoạn code này dùng để "lọc" ra 2 số: N (dạng chuỗi) và K (dạng số) nhé.
- Khi đọc file xong thì chuỗi s sẽ chứa N và K, cách nhau bởi dấu cách trắng.
- Dòng loop for downto sẽ tìm dấu cách nằm ở đâu: bên phải dấu cách sẽ lưu số K, còn bên trái dấu cách sẽ lưu số N. Bởi vậy, dòng lệnh

Mã:

[COLOR=#000000][FONT=Arial]sok:= copy(s,i+1,length(s)-i);[/FONT][/COLOR]

sẽ lưu phần bên phải của chuỗi s vào chuỗi sok.
- Sau đó, lệnh val sẽ đổi giá trị từ chuỗi thành số, và ta đc số K.
- Cuối cùng, khi lấy đc số K rồi thì phải xóa nó khỏi chuỗi s, phần còn lại chính là số N.

vansonqtqb · 17/7/16

cảm ơn bạn rất nhiều..giờ mình đã hiểu rồi...

vansonqtqb · 17/7/16

nhân tiện nhờ bạn xem bài này cho mình un
rong số học, số phong phú là các số mà tổng các ước số của số đó (không kể chính nó) lớn hơn số đó. Ví dụ, số 12 có tổng các ước số (không kể 12) là 1 + 2 + 3 + 4 + 6 = 16 > 12. Do đó 12 là một số phong phú.Bạn hãy lập trình đếm xem có bao nhiêu số phong phú trong đoạn [L,R].[h=3]Dữ liệu[/h]Gồm 2 số L, R (1 <= L <= R <= 105)[h=3]Kết quả[/h]Gồm 1 số nguyên duy nhất là số số phong phú trong đoạn [L, R].[h=3]Chú ý[/h]Có 50% số test có 1 <= L <= R <= 103[h=3]Ví dụ[/h]Dữ liệu
1 50

Kết quả
9

Giải thích:
Từ 1 đến 50 có 9 số phong phú là:
12, 18, 20, 24, 30, 36, 40, 42, 48
Với cách mình của làm thi mình chỉ có thể lấy được 50% số điểm
bạn có thể giúp mình bằng cách phân tích nó thành các thừa số nguyên hay tương tự thuật toán sang nguyên tố được ko? vì khi dữ lệu lớn cách của mình sẽ ko đạt yêu cầu? mong ban hồi âm

tengiday · 17/7/16

Nếu 1 <= L, R <= 105, thì dùng thuật toán nào cũng ko có sự khác biệt lớn lắm đâu. Mình assume rằng bạn biết thuật toán sàng nguyên tố, nếu bạn không muốn dùng mod, div để chia tìm ước số thì dùng thuật toán tương tự như sàng nguyên tố nhé:

Mã:

for i := 2 to right do
   sum[i] := 1;
for i := 2 to right do
   begin
      j := i * 2;
      while (j <= right) do
         begin
            sum[j] := sum[j] + i;
            j := j + i;
         end;
   end;
count := 0;
for i := left to right do
   if sum[i] > i then
      inc(count);

Nếu 'right' lớn thì bạn phải khai báo 'sum' là array of longint nhé.
Nguyên lý chính là:
1) Bội số của số phong phú là 1 số phong phú.
2) Tổng của ước số của 1 bội số của số i thì phải bao gồm tổng của ước số của số i. Để hiểu thêm mảng sum, mình nghĩ bạn nên in giá trị của nó ra.

PS: Thuật toán này của Sieve. Phiên bản mình viết ra cho bạn chỉ là đơn giản nhất.

vansonqtqb · 17/7/16

cảm ơn bạn nhiều. mình ghi nhầm bạn ạ.ý mình ở đây là 10^5 và có thể lớn hơn nữa đó bạn...mình học hỏi được được bạn rất nhiều..

vansonqtqb · 17/7/16

nhờ bạn gửi nguyên chương trình với thuật toán tối ưu nhất cho minh với..thank ban nhiều

tengiday · 18/7/16

vansonqtqb:
nhờ bạn gửi nguyên chương trình với thuật toán tối ưu nhất cho minh với..thank ban nhiều

Về bộ nhớ (space):
- Nếu bạn dùng Turbo Pascal với N lớn tới hàng trăm ngàn hay hơn nữa thì chỉ có thể dùng cách tìm ước rồi tổng của mấy ước đó theo kiểu div, mod bình thường thôi bởi vì Pascal bị giới hạn bộ nhớ (16-bit), ko thể trade bộ nhớ cho tốc độ được.
- Nếu bạn dùng Free Pascal thì cách của mình vẫn chạy được. Khi đó mấy biến chạy là phải longint hết, và có thể dùng mảng kích cỡ lớn.

Về tốc độ:
- Thuật toán mình viết cho bạn có độ phức tạp là O(n log n), khá là tối ưu rồi. Mình chỉ biết còn 1 cách nữa tối ưu hơn xíu (về tốc độ) sử dụng sàng nguyên tố, nhưng nó phức tạp hơn và nói thật, có 1 chỗ mình cũng chưa biết viết thế nào cho đẹp (mình ko phải ngành computer science).

vansonqtqb · 18/7/16

mình phải công nhận bạn nắm rất chắc kiến thức thức lập trình.cảm ơn bạn nhiều..cho mình hỏi thêm luôn nếu theo thuật toán của bạn thì mình có thể in ra được các số pp trong đoạn từ left to right ko bạn.

vansonqtqb · 18/7/16

mình in được các số pp trong đoạn đó rồ. hiện tại đang nghiên cứu thuật toán của bạn.có j ko hiểu mình sẽ hỏi bạn..mong bạ giúp đỡ.thank bạn nhiều

vansonqtqb · 18/7/16

nhờ bạn giải thích lại nguyên lý của thuật toán được không ak.mình ngồi phân tích một chút thấy vẫn lang mang quá..nhờ bạn nói rõ lại thuật toán 1 chút cũng giống như bài xóa số cho mình với......

tengiday · 18/7/16

Phần quan trọng nhất trong thuật toán đó là mảng 'sum', nên mình bắt đầu vào mảng này luôn nhé.

Mã:

sum[J] = tổng các ước số của số J >= 2, không tính chính nó.

(Kết quả của bài toán thì chỉ việc duyệt mảng 'sum', xem coi sum[J] > J hay không).

Nếu I là ước của J (hoặc nói cách khác, J là bội của I), thì ta có thể tính được:

Mã:

sum[J] = sum[J] + I.

(mình đặt I và J như vậy cho nó gần với đoạn code mình viết để dễ theo dõi)

Tới chỗ này là sự khác biệt của thuật toán dùng mod với thuật toán mình ghi đây. Đó là thứ tự của I và J.
- Ở thuật toán dùng mod: chúng ta làm việc với ước của J (duyệt I tìm xem J mod I = 0).
- Ở thuật toán này: chúng ta làm việc với bội của I (dùng trực tiếp J = 2*I, 3*I, 4*I,...). Tại mỗi bội số của I, ta đều cộng vào mảng 'sum' tại chỗ đó giá trị của I.

(I+I, I+I+I, I+I+I+I,.... đều là bội số của I cả).

Khởi tạo mảng 'sum' là 1, tượng trưng cho ước số 1. Như vậy tại mỗi bước I, ta cộng tất cả các bội số J của I một giá trị là I.

Ví dụ: với right = 12:

Ban đầu ta có:

Mã:

index  2  3  4  5  6  7  8  9  10  11  12
sum    1  1  1  1  1  1  1  1   1   1   1

Bắt đầu từ I = 2, bội số của 2 ko tính nó là J = 4, 6, 8, 10, 12. Mình sẽ cộng vào mảng 'sum' tại những vị trí đó giá trị I = 2.

Mã:

index  2  3  [COLOR=#ff0000]4[/COLOR]  5  [COLOR=#ff0000]6[/COLOR]  7  [COLOR=#ff0000]8[/COLOR]  9  [COLOR=#ff0000]10[/COLOR]  11  [COLOR=#ff0000]12[/COLOR]
sum    1  1  [COLOR=#ff0000]3[/COLOR]  1  [COLOR=#ff0000]3[/COLOR]  1  [COLOR=#ff0000]3[/COLOR]  1   [COLOR=#ff0000]3[/COLOR]   1   [COLOR=#ff0000]3[/COLOR]

I = 3, bội số của 3 ko tính nó là J = 6, 9, 12. Mình sẽ cộng vào mảng 'sum' tại những vị trí đó giá trị I = 3.

Mã:

index  2  3  4  5  [COLOR=#ff0000]6[/COLOR]  7  8  [COLOR=#ff0000]9[/COLOR]  10  11  [COLOR=#ff0000]12[/COLOR]
sum    1  1  3  1  [COLOR=#ff0000]6[/COLOR]  1  3  [COLOR=#ff0000]4[/COLOR]   3   1   [COLOR=#ff0000]6[/COLOR]

I = 4, bội số của 4 ko tính nó là J = 8, 12. Mình sẽ cộng vào mảng 'sum' tại những vị trí đó giá trị I = 4.

Mã:

index  2  3  4  5  6  7  [COLOR=#ff0000]8[/COLOR]  9  10  11  [COLOR=#ff0000]12[/COLOR]
sum    1  1  3  1  6  1  [COLOR=#ff0000]7[/COLOR]  4   3   1  [COLOR=#ff0000]10[/COLOR]

Nhìn lại một chút, chúng ta thấy giá trị hiện tại của sum[12] là 10, tượng trưng cho 1 + 2 + 3 + 4 (đều là ước của 12 cả). Tiếp tục cho tới I = 12 thì sẽ điền đc đủ hết tổng các ước số từ 2 tới 12. Đặc điểm của thuật toán này là J nhảy theo bội số mà ko cần đi từng từ phần tử một như cách tìm ước số, bởi vậy độ phức tạp giảm đi, và chương trình chạy nhanh hơn.

vansonqtqb · 21/7/16

ak.mình có ý kiên nhỏ thế này. ko biết bạn nghĩ sao. mình thấy ở đây ta có thế duyệt vòng lặp i thứ 2 đến div 2 là được. không biết ý kiến bạn thế nào?

tengiday · 21/7/16

vansonqtqb:
ak.mình có ý kiên nhỏ thế này. ko biết bạn nghĩ sao. mình thấy ở đây ta có thế duyệt vòng lặp i thứ 2 đến div 2 là được. không biết ý kiến bạn thế nào?

Cám ơn bạn. Vòng lặp i bên ngoài đúng là bạn có thể duyệt tới 'right / 2' là được, ko cần tới 'right' như mình đã ghi. Còn vòng j thì cần giữ nguyên.

vansonqtqb · 21/7/16

ý của mình đây
for i := 2 to b do
sum := 1;
for i := 2 to (b div 2) do

Giải thích giúp mình thuật toán của bài này cho minh với( khó quá)

tengiday

Happy life

phamthanhnhan

(｡◕‿‿◕｡) づ

VSupport

Ngây thơ trong tối

tengiday

Happy life

vansonqtqb

tengiday

Happy life

vansonqtqb

vansonqtqb

tengiday

Happy life

vansonqtqb

vansonqtqb

tengiday

Happy life

vansonqtqb

vansonqtqb

vansonqtqb

tengiday

Happy life

vansonqtqb

tengiday

Happy life

vansonqtqb

Bài viết mới nhất

Thống kê

Bài viết được quan tâm nhiều