1，題目
輸入一個十進制的數，輸出
（1）給定n，求出從1到n的所有整數中1的個數。（暫用用f(n)表示）
（2）求滿足n=f(n)的最大整數（1除外）。
2，思路
首先想到的是字元串比對的方法,但是這個方法比較麻煩,不簡便.
然後實行的方法是把數字排列出來找規律,開始找的規律是
f(10)=2,f(11)=4,f(12)=5......
f(20)=11,f(21)=12,f(22)=12........
.........
即當某位上的數等于1和不等于1時有所不同，當它上一位上等于1時，f(n)會規律性增加。但是這個規律仍是局限于數字的大小。
後來經過讨論，得出的比較合适的方法是根據一個數不同的位數和它周圍位數的關系來總結規律。
以abcde為例，
最高位a，出現1的次數：10000~19999跨度為10000；
第二位b，出現1的次數：1000~1999.跨度為1000；
第三位c，出現1的次數：100~199跨度為100；
。。。。
第0~n -1位組成的數字乘以跨度，然後再根據目前位是大于1，等于1，等于0來加上一個可變的數值。
具體就是，若目前位大于1，則加上跨度；若目前位等于1，則加上該位之後的尾數；若目前位等于0，則加0；具體在個位上時有不同。
3，代碼與截圖
非遞歸算法：
#include<iostream>
using namespace std;
int COUNT(int n)
{
int m = 1;
int count= 0;
cout << "輸入想要查詢的十進制正整數：";
cin >> n;
while (n >= m)
{
int k = 10 * m;
switch((n%k) / m)
{
case 0:
count += (n / k)*m;
break;
case 1:
count += (n / k)*m;
count += n%m + 1;
break;
default:
count += (n / k + 1)*m;
}
m = m * 10;
}
return count;
}
void main()
{
int n=0;
cout << "‘1’的個數為：" <<COUNT(n)<< endl;
} View Code
遞歸算法：
#include<iostream>
using namespace std;
int main()
{
int count = 0, i, N, temp;
cout << "輸入一個十進制的數 :";
cin >> N;
for (i = 1; i <= N; i++)
{
temp = i;//這個地方用個臨時變量記錄i的值
while (temp != 0)
{
count += (temp % 10 == 1) ? 1 : 0;
temp /= 10;
}
if (count == i)
{
cout << "n=f(n)是："<<i << endl;
}
}
cout << "‘1’的個數為：" << count << endl;
return 0;
} 4，總結
遞歸算法來解決問題減少了很多麻煩，很簡便。
實作程式首先要融入和了解數學思維。循環等程式設計方法都是從數學積累而來。
要得到數學規律要基于大量的事實基礎，規律要找對找準。