kết quả từ 1 tới 8 trên 8

Giúp bài tập pascal: Cho một số tự nhiên n>1. Tìm số k nguyên tố không vượt quá n

  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úp bài tập pascal: Cho một số tự nhiên n>1. Tìm số k nguyên tố không vượt quá n

    các bạn giúp mình hai bài này với

    6 Số nguyên tố.

    Cho một số tự nhiên n>1. Tìm số k nguyên tố không vượt quá n trong các trường hợp sau:
    a) k lớn nhất.
    b) k có tổng các chữ số lớn nhất .
    c) k là số đối xứng lớn nhất. ( k là số đối xứng nếu đọc số đó từ trái qua phải hay từ phải qua trái đều như nhau. Ví dụ: các số 373, 3, 979…là các số đối xứng)
    Input cho trong tệp NT.INP:- gồm một dòng duy nhất ghi số nguyên n (1<n<1000001).
    Output ghi vào tệp NT.OUT: gồm 1 dòng, ghi 3 số tương ứng cách nhau bởi dấu cách là đáp số của câu a, b, c. Câu nào không tìm được kết quả thì ghi số 0 thay thế.
    Ví dụ:
    NT.INP NT.OUT
    100 97 89 11


    Phân số ( Đề thi HSG thành phố Hà nội)
    Phân số p/q ( p, q là 2 số nguyên dương) gọi là phân số đúng nếu p/q <1. Còn gọi là phân số tối giản nếu UCLN(p,q)=1
    Yêu cầu: Cho trước số nguyên n (3≤ n ≤ 50000000).
    a) Tính số lượng các phân số đúng, tối giản p/q mà p+q=n.
    b) Tìm phân số đúng, tối giản p/q lớn nhất mà p+q=n.
    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: các bạn giúp mình hai bài này với

    - Bài số nguyên tố đó không khó lắm. Bạn sử dụng những đoạn code cơ bản ghép lại là ra đấy (trừ khi bạn có yêu cầu về thời gian khắt khe).
    - Bài Phân số: bài này nếu duyệt bình thường thì trên máy mình chạy cũng mất khoảng 3 giây. Tuy nhiên, bài này thật ra có thể làm thế này sẽ giảm thời gian còn chưa tới 1 giây; cần có chút kiến thức về số học. Vì p + q = n và gcd(p, q) = 1 nên gcd(p, n) = 1. Như vậy bài này chẳng qua là đếm số co-primes của n mà thôi (sau đó kết quả phải chia 2). Số lượng co-primes của n được cho bởi Euler's Totient function, và nó có công thức rất đẹp dựa trên phân tích thừa số nguyên tố. Riêng câu b thì chỉ việc brute force duyệt tử số ngược từ floor(n / 2) hoặc floor(n / 2) - 1, gặp số đầu tiên thì in ra.
    Mình chỉ viết code câu a thôi nhé, câu b để lại cho bạn.
    Mã:
    procedure proper_fractions(n : longint);
    var count, i: longint;
    begin
        count := n;
        i := 2;
        while (i * i <= n) do
            begin
                if (n mod i = 0) then
                    begin
                        while (n mod i = 0) do
                            n := n div i;
                        count := count - count div i;
                    end;
                inc(i);
            end;
        if (n > 1) then
            count := count - count div n;
        writeln(count div 2);
    end;
    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. #3
    Ðến Từ
    Quảng Bình
    Thành Viên Thứ: 333805
    Giới tính: Nam
    Bài gửi
    62

    Reply: các bạn giúp mình hai bài này với

    bài phân số mình vẫn hiểu mơ hồ quá nhờ bạn giải thích cụ thể cho mình chút được không ak.còn mơ hồ nên nhờ bạn chỉ rõ cả a và b dk ko ak
    -
    PHANSO.INP PHANSO.OUT
    18
    100
    3 7 11
    20 49 51

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

    Reply: Giúp bài tập pascal: Cho một số tự nhiên n>1. Tìm số k nguyên tố không vượt quá n

    Câu a muốn giải nhanh cần biết chút về số học. Những con số p và q cần tìm đều là co-primes với n cả. Công thức tính số lượng co-prime gọi là Euler totient function phi(n).
    Mã:
    phi(n) = n * (1 - 1/p1) * (1 - 1/p2) * (1 - 1/p3) ... với p1, p2, p3,... đều là thừa số nguyên tố khác nhau của n.
    Ứng dụng công thức này hoàn toàn có thể tìm đc tổng số lượng của p và q. Ví p < q nên kết quả cuối cùng phải chia 2. Code của mình tối ưu vì không muốn làm việc với floating point nên giả sử ban đầu có tất cả là n số rồi trừ đi cho những thừa số nguyên tố của n và bội số của chúng.

    Câu b bạn chỉ việc duyệt hết từ lớn tới nhỏ là được mà. Đại khái thế này:
    Mã:
    - Nếu n chẵn thì k := n/2 - 1. Nếu n lẻ thì k := n/2;
    for num := k downto 1 do
        begin
            den := n - num;
            if (gcd(num, den) = 1) then
                begin
                    In ra phân số là 'num/den';
                    break;
                end;
        end;

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

    Reply: Giúp bài tập pascal: Cho một số tự nhiên n>1. Tìm số k nguyên tố không vượt quá n

    Bạn ơi bài số nguyên tố. câu c mình nên xử lí như thế nào hả bạn

  6. #6
    Ðến Từ
    Hà Nội
    Thành Viên Thứ: 358027
    Bài gửi
    1.721

    Reply: Giúp bài tập pascal: Cho một số tự nhiên n>1. Tìm số k nguyên tố không vượt quá n

    Bài: số nguyên tố

    Mã:
    https://vi.wikipedia.org/wiki/S%E1%BB%91_nguy%C3%AAn_t%E1%BB%91
    dùng thuật toán Eratosthene sẽ có được mảng dãy số nguyên tố sắp xếp từ bé đến lớn và nhỏ hơn hoặc bằng n

    a) k lớn nhất => chính là phần tử cuối cùng của mảng

    viết 3 đoạn chương trình con

    chương trình 1: tách số thành từng chữ số, trả lại giá trị gán mảng chữ số (dùng phương pháp chia 10)

    chương trình 2: tính tổng mảng, trả lại giá trị tổng mảng

    chương trình 3: xét mảng có phải đối xứng hay không

    mảng n phần tử

    duyệt i -> (n div 2) nếu a[i] != a[n-i] thì mảng không đối xứng, dừng lặp

    b) chương trình 1 + 2: duyệt từ đầu mảng nguyên tố, nhớ max và vị trí max

    c) chương trình 3: duyệt từ cuối mảng nguyên tố, chỉ cần gặp số nguyên tố đối xứng đầu tiên thì dừng lặp

    Bài phân số:

    p, q >= 0

    p + q = n => p = n - q (1) => 0 =< p, q < n

    p/q < 1 (2)

    (1) thay vào (2) => (n - q)/q < 1 <=> n/q - 1 < 1 <=> n/q < 2 <=> q < n/2

    vậy ta có:

    0 =< q < n/2
    p = n - q

    từ đó ta có thể dễ dàng giải các yêu cầu đầu bài

    duyệt q [0, n/2), tìm p
    [COLOR=#009900][B]www.thuthuatdoday.tk - Chia sẻ thủ thuật, tiện ích máy tính[/B][/COLOR]

  7. #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úp bài tập pascal: Cho một số tự nhiên n>1. Tìm số k nguyên tố không vượt quá n

    Trích Nguyên văn bởi gunshot9x Xem bài viết
    Bài: số nguyên tố

    Mã:
    https://vi.wikipedia.org/wiki/S%E1%BB%91_nguy%C3%AAn_t%E1%BB%91
    dùng thuật toán Eratosthene sẽ có được mảng dãy số nguyên tố sắp xếp từ bé đến lớn và nhỏ hơn hoặc bằng n

    a) k lớn nhất => chính là phần tử cuối cùng của mảng

    viết 3 đoạn chương trình con

    chương trình 1: tách số thành từng chữ số, trả lại giá trị gán mảng chữ số (dùng phương pháp chia 10)

    chương trình 2: tính tổng mảng, trả lại giá trị tổng mảng

    chương trình 3: xét mảng có phải đối xứng hay không

    mảng n phần tử

    duyệt i -> (n div 2) nếu a[i] != a[n-i] thì mảng không đối xứng, dừng lặp

    b) chương trình 1 + 2: duyệt từ đầu mảng nguyên tố, nhớ max và vị trí max

    c) chương trình 3: duyệt từ cuối mảng nguyên tố, chỉ cần gặp số nguyên tố đối xứng đầu tiên thì dừng lặp

    Bài phân số:

    p, q >= 0

    p + q = n => p = n - q (1) => 0 =< p, q < n

    p/q < 1 (2)

    (1) thay vào (2) => (n - q)/q < 1 <=> n/q - 1 < 1 <=> n/q < 2 <=> q < n/2

    vậy ta có:

    0 =< q < n/2
    p = n - q

    từ đó ta có thể dễ dàng giải các yêu cầu đầu bài

    duyệt q [0, n/2), tìm p
    1) Thuật toán này là trường hợp đặc biệt của bài tổng ước số lúc trc mình viết.
    2) p + q = n, p / q < 1 thì p nhỏ hơn n / 2 chứ, q mới lớn hơn n / 2. Tại dòng (1) thay vào (2) last inequality phải đảo dấu lại.

  8. #8
    Ðến Từ
    Hà Nội
    Thành Viên Thứ: 358027
    Bài gửi
    1.721

    Reply: Giúp bài tập pascal: Cho một số tự nhiên n>1. Tìm số k nguyên tố không vượt quá n

    Trích Nguyên văn bởi tengiday Xem bài viết
    1) Thuật toán này là trường hợp đặc biệt của bài tổng ước số lúc trc mình viết.
    2) p + q = n, p / q < 1 thì p nhỏ hơn n / 2 chứ, q mới lớn hơn n / 2. Tại dòng (1) thay vào (2) last inequality phải đảo dấu lại.
    ừ đúng rồi, lâu ngày không động đến bất đẳng thức là thế đó, nghịch đảo nên đổi chiều

    n/q < 2 <=> n/q*1/n < 2*1/n <=> 1/q < 2/n <=> q > n/2

    kết hợp điều kiện

    n/2 < q < n
    p = n - q

    bài toán đặt ra phải sử dụng kiến thức đã học, để phân tích, suy luận đưa ra hướng giải quyết vấn đề => tư duy logic