Trang 1 của 5 123 ... CuốiCuối
Kết quả 1 đến 10 của 47
  1. #1
    Ngày tham gia
    Nov 2015
    Bài viết
    2

    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.

  2. #2
    Ngày tham gia
    Nov 2015
    Bài viết
    3
    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.

  3. #3
    Ngày tham gia
    Nov 2015
    Bài viết
    2
    thuật toán của thớt trên hay nhỉ [IMG]images/smilies/troll2/gach.png[/IMG]

  4. #4
    Ngày tham gia
    Oct 2015
    Bài viết
    140
    tengiday thánh quá, ngưỡng mộ bạn thật [IMG]images/smilies/troll2/xinhqua.png[/IMG]

  5. #5
    Ngày tham gia
    Aug 2015
    Bài viết
    0
    Trích dẫn Gửi bởi VSupport
    tengiday thánh quá, ngưỡng mộ bạn thật [IMG]images/smilies/troll2/xinhqua.png[/IMG]
    Cám ơn bạn, mình chỉ dịch giúp thuật toán của chủ topic thôi.

  6. #6
    Ngày tham gia
    Nov 2015
    Bài viết
    0
    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);

  7. #7
    Ngày tham gia
    Aug 2015
    Bài viết
    6
    [QUOTE="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ã:
    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.

  8. #8
    Ngày tham gia
    Aug 2015
    Bài viết
    0
    cảm ơn bạn rất nhiều..giờ mình đã hiểu rồi...

  9. #9
    Ngày tham gia
    Aug 2015
    Bài viết
    0
    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ệuGồ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

  10. #10
    Ngày tham gia
    Nov 2015
    Bài viết
    0
    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.

 

 
Trang 1 của 5 123 ... CuốiCuối

Quyền viết bài

  • Bạn Không thể gửi Chủ đề mới
  • Bạn Không thể Gửi trả lời
  • Bạn Không thể Gửi file đính kèm
  • Bạn Không thể Sửa bài viết của mình
  •  
Múi giờ GMT +7. Bây giờ là 06:05 PM.
Diễn đàn sử dụng vBulletin® Phiên bản 4.2.5.
Bản quyền của 2024 vBulletin Solutions, Inc. Tất cả quyền được bảo lưu.
Ban quản trị không chịu trách nhiệm về nội dung do thành viên đăng.