Bài 4: Bài toán và thuật toán – Câu 7 trang 44 SGK Tin học 10. Cho N và dãy số a1….aN hãy cho biết có bao nhiêu số hạng trong dãy có giá trị bằng 0. Show
Cho N và dãy số a1….aN hãy cho biết có bao nhiêu số hạng trong dãy có giá trị bằng 0. Xác định bài toán – Input: Qãy A gồm N số nguyên a1, a2.. aN ; – Output: Số số hạng trong dãy A có giá trị bằng 0. Ý tưởng: Tìm kiếm tuần tự được thực hiện một cách tự nhiên. Ta dùng biến đếm k để đếm số số hạng trong dãy A có giá trị bằng 0. Bắt đầu từ i = 7 và mỗi lần tăng i lên 1, ta lần lượt so sánh ai = 0?, nếu ai = 0 thì tăng k lên 1, tiếp tục quá trình cho đến khi i > N thì đưa ra kết quả k và kết thúc. – Thuật toán Cách liệt kê Bước 1. Nhập N, các số hạng a1, a2.. aN Quảng cáoBước 2. i<- k, k<- 0, Bước 3. Nếu ai= 0 thì k <- k+1; Bước 4. i <- i+1 Bước 5: Nếu i > N thì đưa ra giá trị k, rồi kết thúc; Bước 6. Quay lại bước 3. Sơ đồ khối
Viết chương trình in ra màn hình 10 số tự nhiên đầu tiên.
Viết chương trình tính tổng các số từ 1 đến 100. Viết chương trình tính tổng các số từ 1 đến N.
Viết chương trình tổng các số chẵn từ 1 đến N.
Viết chương trình tính N giai thừa.
Viết chương kiểm tra xem N có phải số nguyên tố hay không.
Viết chương trình ra màn hình các số nguyên tố nhỏ hơn N.
Viết chương trình vẽ ra hình chữ nhật có chiều ngang là W, chiều dọc là H, với W và H là 2 số nguyên nhập từ bàn phím.
Viết chương trình nhập không giới hạn số, kết thúc khi nhập vào số 0.
Viết chương trình tìm số hạng thứ N của dãy Fibonacci: 1 ; 1 ; 2 ; 3 ; 5 ; 8 ; 11 ; . . . {\displaystyle 1;1;2;3;5;8;11;...} Viết chương trình in ra màn hình bảng cửu chương N. Viết chương trình in ra N hàng của tam giác Pascal. Viết chương trình in ra tất cả các ký tự có mã ASCII từ M đến N. Cho 4 chữ số 1, 2, 3 và 4. Có bao nhiêu số có 3 chữ số tạo thành từ 4 chữ số 1, 2, 3, 4 và đó là những số nào, viết chương trình thực hiện yêu cầu trên. Gửi tiết kiệm ngân hàng số tiền X đồng với lãi suất N %/tháng. Để nhận được số tiền ít nhất là B đồng thì phải gửi tối thiểu bao nhiêu tháng. Viết chương trình giải quyết bài toán trên trong trường hợp không tính lãi kép.
Chắc hẳn, ai trong chúng ta cũng đã quá quen thuộc với bài toán đếm số ước nguyên dương của nnn. Giải thuật thông thường nhất mà mọi người thường sử dụng là giải thuật O(n),O(\sqrt{n}),O(n), dựa trên một nhận định rằng nếu như số nnn có một ước là i (1≤i≤n)i \ (1 \le i \le \sqrt{n})i (1≤i≤n) thì nó cũng sẽ có một ước nữa là ni (n≤ni≤n)\frac{n}{i} \ \left(\sqrt{n} \le \frac{n}{i} \le n \right)in (n≤in≤n). Bằng phương pháp này, chúng ta có thể giải quyết mọi bài toán với giới hạn nnn khoảng 101510^{15}1015 trở xuống (Các bạn xem lại trong chuyên đề Tìm các ước của một số nguyên). Một phương pháp hay khác mà chúng ta cũng sử dụng là phân tích thừa số nguyên tố và đếm ước của nnn dựa trên phân tích nguyên tố của nó. Cách làm này có thể khiến thao tác đếm ước của số nnn giảm xuống độ phức tạp O(log(n))O(\log(n))O(log(n)) khi kết hợp với sàng lọc số nguyên tố, và thường được áp dụng trong các bài toán multi-testcase (các bạn xem lại trong chuyên đề Số nguyên tố). Tuy nhiên, nhược điểm của phương pháp này là bạn buộc phải tạo ra được một mảng có độ dài nnn để đánh dấu các số nguyên tố, đồng nghĩa với việc nếu n≤109,n \le 10^9,n≤109, các bạn không thể sử dụng được nó. Điều gì sẽ xảy ra khi chúng ta cần đếm ước của một số nguyên dương n≤1018?n \le 10^{18}?n≤1018? Phân tích thừa số nguyên tố? Không thể, vì ta không thể sàng lọc được số nguyên tố ở giới hạn này. Vậy phân tích theo phương pháp O(n)O(\sqrt{n})O(n) truyền thống thì sao? Cũng không thể, vì O(n)≈O(109),O(\sqrt{n}) \approx O(10^9),O(n)≈O(109), độ phức tạp này không đủ tốt. Khi đó, người ta sử dụng phương pháp đếm ước trong O(n13),O(n^{\frac{1}{3}}),O(n31), một phương pháp rất hiệu quả nhưng lại được ít người biết đến, có lẽ vì chúng ta không thường xuyên gặp phải những bài toán như vậy. Trong chuyên đề này, chúng ta sẽ cùng nghiên cứu ý tưởng và cách cài đặt của phương pháp này bằng C++. Trước khi đọc bài viết, các bạn cần có kiến thức đầy đủ về sàng lọc số nguyên tố, đếm ước theo phương pháp thông thường cũng như kĩ năng code ở mức khá. Nếu chưa nắm được những kiến thức này, các bạn hãy quay lại nghiên cứu những chuyên đề cũ mà mình đã để link ở trên nhé! II. Phương pháp đếm số ước của một số trong O(n13)O(n^{\frac{1}{3}})O(n31)Để sử dụng được giải thuật đếm ước trong O(n13),O(n^{\frac{1}{3}}),O(n31), trước tiên ta cần tìm hiểu về phương pháp của Fermat dùng để kiểm tra tính nguyên tố của một số. Đây là một phương pháp kiểm tra nguyên tố có tính xác suất, nghĩa là nó có thể xảy ra trường hợp sai, tuy nhiên, trong giải thuật này sự sai khác đó có thể chấp nhận được. Ý tưởng: Phương pháp kiểm tra tính nguyên tố của Fermat được xây dựng dựa trên định lý Fermat nhỏ: Nếu nnn là một số nguyên tố, thì với mọi giá trị aaa sao cho 1≤a<n1 \le a < n1≤a<n ta đều có: an−1≡1 (mod n)a^{n - 1} \equiv 1 \ (\text{mod }n)an−1≡1 (mod n). Chi tiết chứng minh định lý các bạn có thể đọc thêm ở Wikipedia. Dựa vào định lý trên, ta triển khai giải thuật như sau:
Giải thuật kiểm tra tính nguyên tố của Fermat sẽ luôn luôn đúng nếu như nnn đã là một số nguyên tố, ngược lại nó sẽ có thể sai. Tuy nhiên, như đã nói xác suất xảy ra sai khi nnn là hợp số khá nhỏ, nên chúng ta hoàn toàn có thể sử dụng giải thuật Fermat trong một số trường hợp cụ thể. Bên cạnh đó, các bạn có thể tìm hiểu về một số giải thuật kiểm tra nguyên tố xác suất khác như Miller - Rabin hay Solovay - Strassen. Cài đặt: long long indian_multiplication(long long a, long long b, long long mod) { if (b == 0) return 0LL; long long half = indian_multiplication(a, b / 2LL, mod) % mod; if (b & 1) return (half + half + a) % mod; else return (half + half) % mod; } long long modular_exponentiation(long long a, long long b, long long mod) { if (b == 0) return 1LL; long long half = modular_exponentiation(a, b / 2LL, mod) % mod; long long product = indian_multiplication(half, half, mod); if (b & 1) return indian_multiplication(product, a, mod); else return product; } bool fermat_checking(long long n, int k = 50) { if (n < 4) return n == 2 || n == 3; if (n != 2 && n % 2 == 0) return false; for (int i = 1; i <= k; ++i) { long long a = 2 + rand() % (n - 3); if (modular_exponentiation(a, n - 1, n) != 1) return false; } return true; }Giải thuật có độ phức tạp O(k×log(n))O(k \times \log(n))O(k×log(n)). 2. Phương pháp kiểm tra nguyên tố Miller - RabinPhương pháp nói trên của Fermat có ưu thế là cài đặt đơn giản, ngắn gọn, tuy nhiên xác suất sai sẽ dễ xảy ra trong trường hợp số nnn đưa vào là một số giả nguyên tố (tức là hợp số nhưng vẫn thỏa mãn an≡1 (mod n)a^n \equiv 1 \ (\text{mod }n)an≡1 (mod n) với aaa nào đó). Chính vì thế, khi cần tới độ chính xác cao, người ta thường sử dụng phương pháp kiểm tra tính nguyên tố Miller - Rabin, một phương pháp rất mạnh trong các phương pháp kiểm tra nguyên tố có tính xác suất. Ý tưởng: Giải thuật Miller - Rabin được xây dựng dựa trên một số nhận định sau:
{xk=(xk−1)2;∀k:1≤k≤r.xr=an−1. (4)\begin{cases}x_k = (x_{k - 1})^2;&& \forall k: 1 \le k \le r.\\ x_r = a^{n - 1}. \end{cases} \ (4) {xk=(xk−1)2;xr=an−1.∀k:1≤k≤r. (4)
Dựa vào tất cả các nhận xét trên, ta có mệnh đề kiểm tra nguyên tố Miller - Rabin như sau: Nếu nnn là một số nguyên tố lẻ và n−1=2r×d (r>0,d mod 2≠0)n - 1 = 2^r \times d \ (r > 0, d \text{ mod }2 \ne 0)n−1=2r×d (r>0,d mod 2=0) thì ∀a:1≤a<n,\forall a: 1 \le a < n,∀a:1≤a<n, ta có:
Như vậy giải thuật có thể triển khai thành các bước sau:
Thực hiện giải thuật trên kkk lần, với kkk càng lớn ta sẽ có độ chính xác càng cao. Đối với giải thuật Miller - Rabin thì chỉ cần sử dụng k=10k = 10k=10 là đã đủ an toàn. Cài đặt: int indian_multiplication(int a, int b, int mod) { if (b == 0) return 0; int half = indian_multiplication(a, b / 2LL, mod) % mod; if (b & 1) return (half + half + a) % mod; else return (half + half) % mod; } int modular_exponentiation(int a, int b, int mod) { if (b == 0) return 1LL; int half = modular_exponentiation(a, b / 2LL, mod) % mod; int product = indian_multiplication(half, half, mod); if (b & 1) return indian_multiplication(product, a, mod); else return product; } vector < int > eratosthenes_sieve(int max_value) { vector < bool > is_prime(max_value + 1, true); is_prime[0] = is_prime[1] = false; for (int i = 2; i * i <= max_value; ++i) if (is_prime[i]) for (int j = i * i; j <= max_value; j += i) is_prime[j] = false; vector < int > primes; for (int i = 2; i <= max_value; ++i) if (is_prime[i]) primes.push_back(i); return primes; } bool check_prime_by_miller_rabin(int n, int k) { if (n < 2) return false; if (n != 2 && n % 2 == 0) return false; int d = n - 1; while (d % 2 == 0) d /= 2; for (int i = 1; i <= k; ++i) { int a = rand() % (n - 1) + 1; int temp = d; int mod_val = modular_exponentiation(a, temp, n); while (temp != n - 1 && mod_val != 1 && mod_val != n - 1) { mod_val = indian_multiplication(mod_val, mod_val, n); temp *= 2; } if (mod_val != n - 1 && temp % 2 == 0) return false; } return true; }Giải thuật có độ phức tạp O(k×log(n))O(k \times \log(n))O(k×log(n)). 3. Đếm số ước của một số trong O(n13)O(n^{\frac{1}{3}})O(n31)Ý tưởng: Nói dài dòng như vậy, nhưng bây giờ chúng ta mới đi vào ý chính của bài viết. Trước tiên, ta sẽ viết nnn dưới dạng tích của hai số x,yx, yx,y sao cho:
Dễ dàng nhận thấy, xxx và yyy là hai số nguyên tố cùng nhau, do chúng không có chung bất kỳ thừa số nguyên tố nào cả. Việc tìm ra xxx có thể thực hiện rất dễ, bằng cách duyệt qua tất cả các số nguyên dương trong đoạn [2,n13][2, n^{\frac{1}{3}}][2,n31] và thử chia nnn cho những số đó tới khi không thể chia hết được nữa (giống với cách phân tích thừa số nguyên tố trong O(n)O(\sqrt{n})O(n)). Ở bước này ta sẽ áp dụng thêm sàng lọc số nguyên tố để tìm nhanh ra các số nguyên tố không vượt quá n13n^{\frac{1}{3}}n31. Đến đây, bạn đọc có thể thắc mắc rằng, tại sao lại cần viết nnn ở dạng x×y?x \times y?x×y? Cần biết rằng, hàm F(n)F(n)F(n) đếm số lượng ước nguyên dương của nnn là một Hàm nhân tính, tức là F(n)=F(x)×F(y)F(n) = F(x) \times F(y)F(n)=F(x)×F(y) nếu như xxx và yyy là hai số nguyên tố cùng nhau. Do đó, việc tính F(n)F(n)F(n) sẽ được đưa về việc tính F(x)F(x)F(x) và F(y)F(y)F(y). Cụ thể ta tính F(x)F(x)F(x) và F(y)F(y)F(y) như sau:
Việc kiểm tra yyy thuộc vào trường hợp nào có thể được thực hiện bằng cách sử dụng giải thuật kiểm tra tính nguyên tố của Fermat hoặc Miller - Rabin như mình đã đề cập ở trên! Như vậy, chúng ta đã có thể cài đặt giải thuật đếm số ước của nnn trong O(n13)O(n^{\frac{1}{3}})O(n31)! Cài đặt: Dưới đây là cài đặt C++ của giải thuật, đã được sử dụng để nộp thành công bài tập https://codeforces.com/gym/100753/attachments trên codeforces. Mình sẽ thực hiện bằng cả hai phương pháp kiểm tra số nguyên tố của Fermat và Miller - Rabin. Code bằng giải thuật Fermat: #include <bits/stdc++.h> #define int long long #define task "Divisions_Fermat." using namespace std; vector < int > eratosthenes_sieve(int max_value) { vector < bool > is_prime(max_value + 1, true); is_prime[0] = is_prime[1] = false; for (int i = 2; i * i <= max_value; ++i) if (is_prime[i]) for (int j = i * i; j <= max_value; j += i) is_prime[j] = false; vector < int > primes; for (int i = 2; i <= max_value; ++i) if (is_prime[i]) primes.push_back(i); return primes; } void solution(int n) { vector < int > primes = eratosthenes_sieve(1000000); long long res = 1; for (int p: primes) { if (p * p * p > n) break; int cnt = 0; while (n % p == 0) { n /= p; ++cnt; } res *= (cnt + 1); } if (fermat_checking(n)) res *= 2LL; else { int squaroot = sqrt(n); if (squaroot * squaroot == n && fermat_checking(squaroot)) res *= 3; else if (n != 1) res *= 4; } cout << res; } main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; solution(n); return 0; }Code bằng giải thuật Miller - Rabin: #include <bits/stdc++.h> #define int long long #define task "Divisions_Miller_Rabin." using namespace std; bool sqrt_is_integer(int n) { int squaroot = sqrt(n); return (squaroot * squaroot == n); } void solution(int n, int k) { vector < int > primes = eratosthenes_sieve(1000000); long long res = 1; for (int p: primes) { if (p * p * p > n) break; int cnt = 0; while (n % p == 0) { n /= p; ++cnt; } res *= (cnt + 1); } if (check_prime_by_miller_rabin(n, k)) res *= 2LL; else if (sqrt_is_integer(n) && check_prime_by_miller_rabin((int)sqrt(n), k)) res *= 3LL; else if (n != 1) res *= 4LL; cout << res; } main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; solution(n, 10); return 0; }III. Tài liệu tham khảo |