Chúng ta được cho một số tự nhiên, gọi là num, và nhiệm vụ là tính số lượng tất cả các số tự nhiên mà mọi hoán vị của chúng đều lớn hơn hoặc bằng số đó.
Chúng ta làm việc với các điều kiện sau −
Dữ liệu chỉ nên là số tự nhiên
Tất cả các hoán vị hoặc sắp xếp có thể của một số tự nhiên phải bằng hoặc lớn hơn số cho trước. Ví dụ, số là 20
Xét tất cả các số đến 20 bắt đầu từ 1: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
Kiểm tra các số mà hoán vị của chúng bằng hoặc lớn hơn số cho trước, tức là 20. Các số là 1, 2, 3, 4, 5, 6, 7, 8, 9, 11=11, 12<21, 13<31, 14<41, 15<51, 16<61, 17<71, 18<81, 19<91. Vậy đếm sẽ là 18.
Đầu vào − num = 10
Đầu ra − đếm là 9
Giải thích − Các số 1, 2, 3, 4, 5, 6, 7, 8, 9 là các số bằng nhau khi sắp xếp theo bất kỳ cách nào.
Đầu vào − num = 13
Đầu ra − đếm là 12
Giải thích − Các số 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12<21, 13<31 là các số bằng hoặc lớn hơn số cho trước khi sắp xếp theo bất kỳ cách nào.
Phương pháp sử dụng trong chương trình dưới đây như sau
Nhập giá trị của số num
Đặt max_size thành 9 vì luôn có ít nhất 9 số có hoán vị bằng hoặc lớn hơn chính nó.
Bắt đầu vòng lặp từ 0 đến max_size
Trong vòng lặp, tạo biến kiểu list và kiểm tra nếu i nhỏ hơn hoặc bằng num NẾU có thì chèn i vào list và tăng đếm lên 1
Duyệt list từ cuối về đầu và bắt đầu vòng lặp khác từ phần tử đầu tiên đến 9.
Kiểm tra nếu temp <= num thì đẩy temp vào đầu list và tăng đếm lên 1
Trả về đếm
In kết quả.
Ví dụ
#include<bits/stdc++.h> using namespace std; //function to Count natural numbers whose //all permutation are greater than that number void count(int num){ int count = 0; int max_size = 9; for (int i = 1; i <= max_size; i++){ list<int> lists; if (i <= num){ //chèn phần tử vào cuối list lists.push_back(i); count = count + 1; } //iterator bắt đầu từ cuối list for(auto iter = lists.end(); iter != lists.begin(); ++iter){ int first_ele = lists.front(); lists.pop_front(); for (int next = first_ele%10; next <= 9; next++){ int temp = first_ele*10 + next; if (temp <= num){ lists.push_front(temp); count++; } } } } cout<<"count of num "<<num <<" is "<<count<<endl; } int main(){ count(1); count(9); count(7); count(0); count(12); return 0; } Đầu ra
Nếu chúng ta chạy mã trên, chúng ta sẽ nhận được đầu ra sau −
count of num 1 is 1 count of num 9 is 9 count of num 7 is 7 count of num 0 is 0 count of num 12 is 11