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

vansonqtqb · 8/11/16

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.

tengiday · 9/11/16

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.
[ah]

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;

[/ah]

vansonqtqb · 9/11/16

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

tengiday · 10/11/16

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

.

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;

vansonqtqb · 13/11/16

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

gunshot9x · 13/11/16

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 != 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

tengiday · 13/11/16

gunshot9x:
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 != 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.

gunshot9x · 14/11/16

tengiday:
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

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

tengiday

Happy life

vansonqtqb

tengiday

Happy life

vansonqtqb

gunshot9x

tengiday

Happy life

gunshot9x

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

Thống kê

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