Giải Thích Giúp Mình Thuật Toán Của Bài Này Cho Minh Với( Khó Quá)

Forum

• 
• Diễn đàn
• Mới nhất
• Công nghệ
• Điện thoại
• Máy tính
• Xe
• Thủ Thuật
• Hỏi đáp

Đăng nhập News Feed

Tìm kiếm

Mọi thứ Chủ đề Diễn đàn này Chủ đề này Chỉ tìm trong tiêu đề Bởi: Tìm Tìm kiếm nâng cao… Menu Đăng nhập Đăng ký Install the app Cài đặt You are using an out of date browser. It may not display this or other websites correctly.You should upgrade or use an alternative browser.

• Lập Trình - Đồ họa - Web
• Lập trình
• Pascal

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

• 1
• 2
• 3

Tiếp 1 of 3

Đi đến trang

Tới Tiếp Last 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 có M chữ số. (1 Yêu cầu: Xóa đi K chữ số trong N để thu được số N’ sao cho N’ có giá trị nhỏ 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: Dòng 1: Ghi số hai số nguyên dương N K. Hai số được ghi cách nhau ít nhất một dấu cách. Dữ liệu ra: Ghi ra file văn bản XOASO.OUT theo cấu trúc như sau: Dòng 1: Ghi số N’ tìm được. (Vẫn giữ các chữ số 0 ở đầu số nếu có) Ví dụ:

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

> const fi='xoaso.in7'; fo='xoasU7'; 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. Sửa lần cuối bởi điều hành viên: 15/7/16 T

tengiday

Happy life

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. P

phamthanhnhan

(｡◕‿‿◕｡) づ

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ỉ

VSupport

Ngây thơ trong tối

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

tengiday

Happy life

VSupport: tengiday thánh quá, ngưỡng mộ bạn thật Nhấn để mở rộng...

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

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 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); T

tengiday

Happy life

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] Nhấn để mở rộng...

Đ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. V

vansonqtqb

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

vansonqtqb

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 T

tengiday

Happy life

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. V

vansonqtqb

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.. V

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 T

tengiday

Happy life

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 Nhấn để mở rộng...

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). V

vansonqtqb

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. V

vansonqtqb

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 V

vansonqtqb

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...... T

tengiday

Happy life

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. V

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? T

tengiday

Happy life

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? Nhấn để mở rộng...

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. V

vansonqtqb

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

• 1
• 2
• 3

Tiếp 1 of 3

Đi đến trang

Tới Tiếp Last Đăng nhập bằng tài khoản VFO hoặc Facebook Google

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

• Kho truyện ngắn cực hay
  • shopoga
  • 19:46 Hôm qua
• Sách Hay Mỗi Ngày
  • shopoga
  • 19:43 Hôm qua
• Trải nghiệm thực tế chuột chơi game Razer Viper V3 Pro
  • Tuấn Hà
  • 17:50 Hôm qua
• T Huawei ra mắt Mate X6 tại thị trường quốc tế
  • Tin Tức
  • 08:54 Hôm qua
• T Lộ diện ảnh thực tế và thông tin phần cứng Honor GT
  • Tin Tức
  • 08:27 Hôm qua

Thống kê

Chủ đề 101,993 Bài viết 469,403 Thành viên 340,319 Thành viên mới nhất kien01

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

• T Huawei ra mắt Mate X6 tại thị trường quốc tế
  • Tin Tức
  • 08:54 Hôm qua
• T Lộ diện thông số kỹ thuật Google Pixel 9a
  • Tin Tức
  • 07:55 Hôm qua
• T Lộ diện ảnh thực tế và thông tin phần cứng Honor GT
  • Tin Tức
  • 08:27 Hôm qua
• Trải nghiệm thực tế chuột chơi game Razer Viper V3 Pro
  • Tuấn Hà
  • 17:50 Hôm qua

Top