Trang 1/5 123 ... cuối
kết quả từ 1 tới 12 trên 57

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

  1. #1
    Ðến Từ
    Quảng Bình
    Thành Viên Thứ: 333805
    Giới tính: Nam
    Bài gửi
    62

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

    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='xoaso.OU7';
    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[i]=' ' 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.
    Quick reply to this message Trả lời       


  2. #2
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    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.
    LCD: 13.3" 1920x1080 IPS
    CPU: Intel i7 - 4700MQ (2.4 GHz - 3.4 GHz)
    GPU: Nvidia GTX 765m with GDDR5 2GB
    RAM: 2x8GB G.Skill 2133
    HDD: Samsung SSD 850 Pro 512 GB
    2 kg.

  3. 4 thành viên đã cảm ơn tengiday:


  4. #3
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 261001
    Giới tính: Nam
    Bài gửi
    1.008

    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ỉ

  5. Đã cảm ơn phamthanhnhan:


  6. #4
    Ðến Từ
    Hà Nội
    Thành Viên Thứ: 247344
    Giới tính: Nữ
    Bài gửi
    10.089

    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á)

    tengiday thánh quá, ngưỡng mộ bạn thật
    Thực sự thì mình chưa thấy ai lại hiền lành, dễ thương và tốt bụng như bạn Khách vậy

  7. 2 thành viên đã cảm ơn VSupport:


  8. #5
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    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á)

    Trích Nguyên văn bởi VSupport Xem bài viết
    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.

  9. #6
    Ðến Từ
    Quảng Bình
    Thành Viên Thứ: 333805
    Giới tính: Nam
    Bài gửi
    62

    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á)

    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[i]=' ' 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);

  10. #7
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    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á)

    Trích Nguyên văn bởi vansonqtqb Xem bài viết
    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ã:
    for i:=length(s) downto 1 do if s[i]=' ' 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);
    
    Đ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ã:
    sok:= copy(s,i+1,length(s)-i);
    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.

  11. Đã cảm ơn tengiday:


  12. #8
    Ðến Từ
    Quảng Bình
    Thành Viên Thứ: 333805
    Giới tính: Nam
    Bài gửi
    62

    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á)

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

  13. #9
    Ðến Từ
    Quảng Bình
    Thành Viên Thứ: 333805
    Giới tính: Nam
    Bài gửi
    62

    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á)

    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].Dữ liệu

    Gồm 2 số L, R (1 <= L <= R <= 105)Kết quả

    Gồm 1 số nguyên duy nhất là số số phong phú trong đoạn [L, R].Chú ý

    Có 50% số test có 1 <= L <= R <= 103Ví dụ

    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

  14. #10
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    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á)

    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.

  15. 2 thành viên đã cảm ơn tengiday:


  16. #11
    Ðến Từ
    Quảng Bình
    Thành Viên Thứ: 333805
    Giới tính: Nam
    Bài gửi
    62

    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á)

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

  17. Đã cảm ơn vansonqtqb:


  18. #12
    Ðến Từ
    Quảng Bình
    Thành Viên Thứ: 333805
    Giới tính: Nam
    Bài gửi
    62

    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á)

    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

Trang 1/5 123 ... cuối