Hiển thị kết quả từ 1 đến 10 / 10
  1. #1
    Tham gia
    15-11-2010
    Bài viết
    38
    Like
    0
    Thanked 2 Times in 2 Posts

    Tệ thật ! Giúp tôi bài Pascal này nưa

    bài 1:
    Tìm K chữ số cuối cùng của M^N (0<k<=9, 0<=m,n<=10^9)
    vd: k= 2, m=2, n=10
    ta co 2^10=1024, như vậy 2 chữ số cuối cùng của 2^10 là 24
    bài 2:Dãy con lồi
    dãy số nguyên á,à,..aN được gọi là lồi nếu nó giảm dần từ a1 đến 1 ai nào đó, rồi tăng dần tới an
    vd: dãy lồi : 10 5 4 2 -1 4 6 8 12
    yêu cầu: Cho 1 dãy số nguyên, bằng cách xóa bớt 1 số phần tử của dãy và giữ nguyên trình tự các phần tử còn lại, ta nhận được dãy con lồi dài nhất
    input: tep ds.inp
    - dòng đầu là N (N<=10000)
    - Các dòng sau là N số nguyên của dãy số ( các số kiểu longint)
    output: tep ds.out
    - Ghi số phần tử của dãy con tìm được
    - Các dòng tiếp theo ghi các số thuộc dãy con.
    Quote Quote

  2. #2
    Tham gia
    29-05-2011
    Location
    Hà Nội
    Bài viết
    1,826
    Like
    1,420
    Thanked 47 Times in 42 Posts
    bài 1:
    Tìm K chữ số cuối cùng của M^N (0<k<=9, 0<=m,n<=10^9)
    vd: k= 2, m=2, n=10
    ta co 2^10=1024, như vậy 2 chữ số cuối cùng của 2^10 là 24
    Code:
    Uses crt;
    {------------------------------------------------------------------}
    Function BT(a,n:integer):longint;
    Var
      s:longint;
      i:integer;
    Begin
      s:=1;
      For i:=1 to n do s:=s*a;
      BT:=s;
    End;
    {------------------------------------------------------------------}
    Var
      s:string;
      m,n,k,a,d:longint;
    BEGIN
      Clrscr;
      Write('Nhap so m,n,k:');
      Readln(m,n,k);
      a:=BT(m,n);
      Str(a,s);
      d:=Length(s)-k;
      Delete(s,1,d);
      Write(s);
      Readln;
    END.
    Bài này mình chưa test, nếu sai thì bạn bảo mình nhé !

  3. #3
    Tham gia
    05-08-2010
    Bài viết
    313
    Like
    9
    Thanked 73 Times in 69 Posts
    Quote Được gửi bởi auauau97 View Post
    Code:
    Uses crt;
    {------------------------------------------------------------------}
    Function BT(a,n:integer):longint;
    Var
      s:longint;
      i:integer;
    Begin
      s:=1;
      For i:=1 to n do s:=s*a;
      BT:=s;
    End;
    {------------------------------------------------------------------}
    Var
      s:string;
      m,n,k,a,d:longint;
    BEGIN
      Clrscr;
      Write('Nhap so m,n,k:');
      Readln(m,n,k);
      a:=BT(m,n);
      Str(a,s);
      d:=Length(s)-k;
      Delete(s,1,d);
      Write(s);
      Readln;
    END.
    Bài này mình chưa test, nếu sai thì bạn bảo mình nhé !
    Bài của auauau97 chỉ đúng với m, n nhỏ thôi, nếu lớn hơn là ko làm được đâu.

    Vì k<=9 nên chỉ cần lưu k chữ số của kết quả, nếu lưu hết thì sẽ tràn số, vì longint chỉ đến 2 tỷ trong khi m, n có thể = 10^9
    Ngoài ra các chữ số tận cùng còn lặp lại nên có thể dựa vào đó để tính nhanh hơn

  4. #4
    Tham gia
    29-05-2011
    Location
    Hà Nội
    Bài viết
    1,826
    Like
    1,420
    Thanked 47 Times in 42 Posts
    Quote Được gửi bởi HGMinh95 View Post
    Bài của auauau97 chỉ đúng với m, n nhỏ thôi, nếu lớn hơn là ko làm được đâu.

    Vì k<=9 nên chỉ cần lưu k chữ số của kết quả, nếu lưu hết thì sẽ tràn số, vì longint chỉ đến 2 tỷ trong khi m, n có thể = 10^9
    Ngoài ra các chữ số tận cùng còn lặp lại nên có thể dựa vào đó để tính nhanh hơn
    Nếu m,n lớn thì ta có thể dùng xâu để tính rồi chuyển sang số nhỉ ?

  5. #5
    Tham gia
    05-08-2010
    Bài viết
    313
    Like
    9
    Thanked 73 Times in 69 Posts
    Quote Được gửi bởi bin yeu View Post
    bài 1:
    bài 2:Dãy con lồi
    dãy số nguyên á,à,..aN được gọi là lồi nếu nó giảm dần từ a1 đến 1 ai nào đó, rồi tăng dần tới an
    vd: dãy lồi : 10 5 4 2 -1 4 6 8 12
    yêu cầu: Cho 1 dãy số nguyên, bằng cách xóa bớt 1 số phần tử của dãy và giữ nguyên trình tự các phần tử còn lại, ta nhận được dãy con lồi dài nhất
    input: tep ds.inp
    - dòng đầu là N (N<=10000)
    - Các dòng sau là N số nguyên của dãy số ( các số kiểu longint)
    output: tep ds.out
    - Ghi số phần tử của dãy con tìm được
    - Các dòng tiếp theo ghi các số thuộc dãy con.
    Bài này bạn có thể dùng QHĐ để giải

    Thêm 2 phần tử a[0]= + vô cùng và a[n+1]= - vô cùng vào dãy

    Gọi G[i] là độ dài dãy con đơn điệu giảm dài nhất từ đầu dãy -> phần tử thứ i , G[n]=0
    Hàm Max(j,b) trả về số i sao cho G[i] lớn nhất trong đoạn từ G[0]->G[j] thỏa mãn a[j]<b

    Tính G[i] theo công thức G[i]=G[Max(i,a[i])]+1

    Tương tự như vậy bạn tính T[i] là độ dài dãy con đơn điệu tăng dài nhất bắt đầu từ phần tử i -> n+1

    Sau đó tính G[i]+T[i] max là độ dài dãy con lồi dài nhất

    Phần truy vết thì mình chưa nghĩ ra

  6. #6
    Tham gia
    15-11-2010
    Bài viết
    38
    Like
    0
    Thanked 2 Times in 2 Posts
    mình cám ơn mọi người nhiều lắm!
    Mình mới đang bắt đầu học lập trình nên rất kém! mong mọi người giúp đỡ.
    bài 2 mình hiểu rùi nhưng bài 1 các bạn có thể nói cho mình biết thuật toán đc k?
    thanks!!!!!!!!

    [=========> Bổ sung bài viết <=========]

    Quote Được gửi bởi HGMinh95 View Post
    Bài của auauau97 chỉ đúng với m, n nhỏ thôi, nếu lớn hơn là ko làm được đâu.

    Vì k<=9 nên chỉ cần lưu k chữ số của kết quả, nếu lưu hết thì sẽ tràn số, vì longint chỉ đến 2 tỷ trong khi m, n có thể = 10^9
    Ngoài ra các chữ số tận cùng còn lặp lại nên có thể dựa vào đó để tính nhanh hơn
    bạn nói giúp mình ý tưởng của bạn đi
    Được sửa bởi bin yeu lúc 22:04 ngày 25-06-2011 Reason: Bổ sung bài viết

  7. #7
    Tham gia
    25-06-2011
    Location
    Ninh Bình
    Bài viết
    165
    Like
    4
    Thanked 57 Times in 52 Posts

    Thông tin

    Quote Được gửi bởi auauau97 View Post
    Code:
    Uses crt;
    {------------------------------------------------------------------}
    Function BT(a,n:integer):longint;
    Var
      s:longint;
      i:integer;
    Begin
      s:=1;
      For i:=1 to n do s:=s*a;
      BT:=s;
    End;
    {------------------------------------------------------------------}
    Var
      s:string;
      m,n,k,a,d:longint;
    BEGIN
      Clrscr;
      Write('Nhap so m,n,k:');
      Readln(m,n,k);
      a:=BT(m,n);
      Str(a,s);
      d:=Length(s)-k;
      Delete(s,1,d);
      Write(s);
      Readln;
    END.
    Bài này mình chưa test, nếu sai thì bạn bảo mình nhé !
    Bài này n<= 10^9, nếu làm như bạn thì chắc đợi cả tiếng!

  8. #8
    Tham gia
    29-05-2011
    Location
    Hà Nội
    Bài viết
    1,826
    Like
    1,420
    Thanked 47 Times in 42 Posts
    Quote Được gửi bởi bin yeu View Post
    mình cám ơn mọi người nhiều lắm!
    Mình mới đang bắt đầu học lập trình nên rất kém! mong mọi người giúp đỡ.
    bài 2 mình hiểu rùi nhưng bài 1 các bạn có thể nói cho mình biết thuật toán đc k?
    thanks!!!!!!!!

    [=========> Bổ sung bài viết <=========]



    bạn nói giúp mình ý tưởng của bạn đi
    Bài 1 thì trước tiên, ta lập 1 hàm tính a^n (để bắt tính m^n mà).
    Để tính a^n(trường hợp tổng quát), ta cho 1 biến s=a*a*a*a*a...*a(n lần *a) bằng cách cho vòng for từ 1 tới n:
    For i:=1 to n do
    lỗi lần i tăng thì là 1 lần nhân s với a:
    s:=s*a;
    cuối cùng gán BT:=s vì đây là Function,.
    Chẳng hạn:
    a=2 và n=3, ta có:
    gán s:=1 trước tiên
    For i:=1 to n do s:=s*a thành:
    For i:=1 to 3 do s:=s*2
    i=1 thì s=s*a=1*2=2
    i=2 thì s=s*a=2*2=4(vì ở trên, s đã =2 rồi, nhân tiếp với a=2 nữa là 4)
    i=3 thì s=s*a=4*2=8
    Nên s=8, cuối cùng, ta gán BT=8 là xong hàm tính a^n.
    Code:
    Write('Nhap so m,n,k:');
    Readln(m,n,k);{nhập m,n,k theo để bài}
    a:=BT(m,n);{tính m^n theo hàm tính a^n ở trên, ở đây m là a và n vẫn là n.Và ta gán m^n=1 biến có tên a }
    Str(a,s);{bước này đổi a thành xâu s}
    d:=Length(s)-k;{ta tính hiệu của độ dài của xâu s với k(length(s)-k) và gán vào biến d}
    Delete(s,1,d);{lệnh này để xóa d ký tự của xâu s bắt đầu từ vị trí 1, khi đó xâu s chỉ còn số k ký tự cuối mà ta cần}
    Write(s);{In ra xâu còn lại}
    VD:
    m=2
    n=5
    k=1;
    a:=BT(m,n)=2^5=32(tính như ở trên)
    gán a vào xâu s (str(a,s)) nên s='25';
    Length(s)=2 (độ dìa của xâu =2)
    d:=length(s)-k=2-1=1
    Delete(s,1,d) thành Delete(s,1,1), xóa 1 ký tự của xâu s, bắt đầu từ ký tự đầu tiên:
    s='25', sau lệnh delete, s='5'
    In ra 5 và thoát !

    [=========> Bổ sung bài viết <=========]

    Quote Được gửi bởi haplinhavxt View Post
    Bài này n<= 10^9, nếu làm như bạn thì chắc đợi cả tiếng!
    Nếu bạn dùng Free Pascal và khái báo m,n,k là int64 thì không đến nỗi đâu !
    Khai báo luôn cả a,n trong FUnction là int64 nữa cũng tốt !
    Được sửa bởi auauau97 lúc 08:50 ngày 26-06-2011 Reason: Bổ sung bài viết

  9. #9
    Tham gia
    25-06-2011
    Location
    Ninh Bình
    Bài viết
    165
    Like
    4
    Thanked 57 Times in 52 Posts
    Bài này giới bạn của m, n là <= 10^9 nên theo mình là dựa vào nhận xét là các chữ số tận cùng còn lặp lại nên có thể dựa vào đó để tính nhanh hơn là cách trâu bò kia!

  10. #10
    Tham gia
    05-08-2010
    Bài viết
    313
    Like
    9
    Thanked 73 Times in 69 Posts
    Quote Được gửi bởi auauau97 View Post
    Bài 1 thì trước tiên, ta lập 1 hàm tính a^n (để bắt tính m^n mà).
    Để tính a^n(trường hợp tổng quát), ta cho 1 biến s=a*a*a*a*a...*a(n lần *a) bằng cách cho vòng for từ 1 tới n:
    For i:=1 to n do
    lỗi lần i tăng thì là 1 lần nhân s với a:
    s:=s*a;
    cuối cùng gán BT:=s vì đây là Function,.
    Chẳng hạn:
    a=2 và n=3, ta có:
    gán s:=1 trước tiên
    For i:=1 to n do s:=s*a thành:
    For i:=1 to 3 do s:=s*2
    i=1 thì s=s*a=1*2=2
    i=2 thì s=s*a=2*2=4(vì ở trên, s đã =2 rồi, nhân tiếp với a=2 nữa là 4)
    i=3 thì s=s*a=4*2=8
    Nên s=8, cuối cùng, ta gán BT=8 là xong hàm tính a^n.
    Code:
    Write('Nhap so m,n,k:');
    Readln(m,n,k);{nhập m,n,k theo để bài}
    a:=BT(m,n);{tính m^n theo hàm tính a^n ở trên, ở đây m là a và n vẫn là n.Và ta gán m^n=1 biến có tên a }
    Str(a,s);{bước này đổi a thành xâu s}
    d:=Length(s)-k;{ta tính hiệu của độ dài của xâu s với k(length(s)-k) và gán vào biến d}
    Delete(s,1,d);{lệnh này để xóa d ký tự của xâu s bắt đầu từ vị trí 1, khi đó xâu s chỉ còn số k ký tự cuối mà ta cần}
    Write(s);{In ra xâu còn lại}
    VD:
    m=2
    n=5
    k=1;
    a:=BT(m,n)=2^5=32(tính như ở trên)
    gán a vào xâu s (str(a,s)) nên s='25';
    Length(s)=2 (độ dìa của xâu =2)
    d:=length(s)-k=2-1=1
    Delete(s,1,d) thành Delete(s,1,1), xóa 1 ký tự của xâu s, bắt đầu từ ký tự đầu tiên:
    s='25', sau lệnh delete, s='5'
    In ra 5 và thoát !

    Nếu bạn dùng Free Pascal và khái báo m,n,k là int64 thì không đến nỗi đâu !
    Khai báo luôn cả a,n trong FUnction là int64 nữa cũng tốt !
    Cho dù bạn dùng int64 nhưng nếu m^n có thể bằng (10^9)^(10^9) = 100...00 ( 9 tỷ số 0), ko biết có kiểu dự liệu nào chứa được ko?

    Quote Được gửi bởi bin yeu View Post
    mình cám ơn mọi người nhiều lắm!
    Mình mới đang bắt đầu học lập trình nên rất kém! mong mọi người giúp đỡ.
    bài 2 mình hiểu rùi nhưng bài 1 các bạn có thể nói cho mình biết thuật toán đc k?
    thanks!!!!!!!!
    bạn nói giúp mình ý tưởng của bạn đi
    Ý tưởng mình cũng nói rồi mà. Bạn viết 1 hàm Caculate(a, b, k: longint): longint tính tích của 2 số a, b, trả về kết quả là k chữ số tận cùng của a*b. Vì a*b có thể > longint nên bạn ko thể tính theo cách thông thường (cách gì thì bạn tự làm nhé )

    Code:
    S:= m
    for i:=2 to n do
        S:=Caculate(m,S,k);
    Nếu chương trình chạy chậm thì bạn có thể tạo 1 mảng a lưu chữ k chữ số tận cùng của m^1, m^2,... cho đến m^i mà k chữ số tận cùng của nó = k chữ số tận cùng của m^1. Từ đó tính thẳng ra kq mà ko cần tính m^n.
    Được sửa bởi HGMinh95 lúc 15:38 ngày 26-06-2011 Reason: Bổ sung bài viết

Bookmarks

Quy định

  • Bạn không thể tạo chủ đề mới
  • Bạn không thể trả lời bài viết
  • 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
  •