算法实现题1

1-1 统计数学问题方法一：暴力方法二：拆分（其实是递归） 1-2 字典序问题

1-1 统计数学问题

方法一：暴力

#include<iostream> using namespace std; int main() { int listNum[10] = { 0 }; int n; cin >> n; for (int i = 1; i <= n; i++) { int tmp = i; while (tmp) { listNum[tmp % 10]++; tmp = tmp / 10; } } for (int i = 0; i <= 9; i++) { cout << listNum[i] << endl; } return 0; }

方法二：拆分（其实是递归）

用int listNum[10] 中 listNum[0]~listNum[9] 代表 0-9 出现的次数

1.求n的最高位length len = log(n)+1

2.划分区间 易知

位数次数0~9每个数字出现1次00~99每个数字出现20次000~999每个数字出现300次……0…0~9…9(k个0与9)每个数字出现 k * 10^(k - 1) 次

按数最高位来划分，每一个数 n 都有区间数为 Interval = n / (10^(len - 1)) 如4321，可分为 000-999，1000-1999，2000-2999，3000-3999 那么，除了最高位，这每一个区间内0-9出现的次数是 (len-1)*10^(len-2) 综上，除了最高位，如4321，000-3999中0-9出现次数为 Interval * (len-1)*10^(len-2)

3.最高位 下以4321为例，计算000-3999中最高位所带来的0-9次数 0：0000-0999，1000个0 1：1000-1999，1000个1 2：2000-2999，1000个2 3：3000-3999，1000个3 最高位为m，那么有

for(int i=0;i<m;i++) { listNum[i] += pow(10,len - 1); } listNum[m] += 1 + n % (pow(10, len - 1));

4.去掉最高位递归 再递归调用 nextN = n % (10^(len - 1)) 其中， (1)若nextN为0，此时 listNum[0] 要加 len - 1。然后结束递归 (2)若nextN不为0，如果 lenNextN != len-1，那么 listNum[0] += (len - lenN - 1)*(nextN + 1)。

5.递归结束处理0

for(int i=0;i<len;i++) { c[0] -= pow(10,i)); }

代码如下

#include<iostream> #include<cstdio> #include<cmath> using namespace std; int listNum[10]; void function1(int n) { //求n的最高位length int len = log10(n) + 1; //划分区间 int interval = n / ((int)round(pow(10.0, len - 1))); for(int i = 0; i < 10; i++) { listNum[i] += interval * (len - 1) * (int)round(pow(10.0,len - 2)); } //最高位 int m = n / ((int)round(pow(10.0, len - 1)));//最高位的值 for (int i = 0; i < m; i++) { listNum[i] += (int)round(pow(10.0, len - 1)); } listNum[m] += 1 + n % (int)round(pow(10, len - 1)); int nextN = n % (((int)round(pow(10.0, len - 1)))); if (nextN == 0) { listNum[0] += len - 1; return; } int lenN = log10(nextN) + 1; if (lenN != len - 1) listNum[0] += (len - lenN - 1) * (nextN + 1); return function1(nextN); } int main() { fill(listNum, listNum + 10, 0); int n; cin >> n; int len = log10(n) + 1; function1(n); //处理0 for (int i = 0; i < len; i++) { listNum[0] -= (int)round(pow(10.0, i)); } //展示 for (int i = 0; i <= 9; i++) { cout << listNum[i] << endl; } return 0; }

1-2 字典序问题

如果字符串长度为len，那么该字符串共有有C(26, len)个 所以，欲求xyz的值，先将字符串长度为1，字符串长度为2的个数相加：

int sum = 0; for(int i = 1; i < s.size(); i++)//s.size() - 1位之前的组合数 sum += C(26, i);

下求字符串长度为3的之前的值。 以ekt为例，可以看到， e_ _ 之前是 a_ _ 、b_ _ 、 c_ _ 、… 、d _ _ 。 ek _ 之前是 ef_ 、eg_ 、 eh_ 、… 、ej _ 。 ekt 之前是 ekl 、ekm 、 ekn 、… 、eks 。 依次求它们的数目 为：

for (int i = 0; i < s.size(); i++) { int x = 0; if (i != 0) x = s[i - 1] - 'a' + 1;//利用x来维护每次组合差的起点，后一位的起点必定为前一位字母的后继。 //如果一个字符串的s[i - 1]、s[i]为xy，那么从x开始 //对每一位的组合进行求和 //具体过程为第i-1位初始数对应剩下26-x个数进行组合后 //减去 //第i位对应剩下26-(s[i]-'a')个数进行组合 sum += C(26 - x, s.size() - i) - C(26 - (s[i] - 'a'), s.size() - i); }

代码如下

#include<iostream> #include<string> using namespace std; int C(int n, int m)//组合数 { if (n == m || 0 == m || 0 == n || n == 1) { return 1; } return C(n - 1, m) + C(n - 1, m - 1); } int main() { int rank; string s; cin >> rank; while (rank) { cin >> s; if (s.size() == 1)//一个字母 { cout << s[s.size() - 1] - 'a' + 1; continue; } //多个字母 int sum = 0; for(int i = 1; i < s.size(); i++)//s.size() - 1位之前的组合数 sum += C(26, i); for (int i = 0; i < s.size(); i++) { int x = 0; if (i != 0) x = s[i - 1] - 'a' + 1;//利用x来维护每次组合差的起点，后一位的起点必定为前一位字母的后继。 //如果一个字符串的s[i - 1]、s[i]为xy，那么从x开始 //对每一位的组合进行求和 //具体过程为第i-1位初始数对应剩下26-x个数进行组合后 //减去 //第i位对应剩下26-(s[i]-'a')个数进行组合 sum += C(26 - x, s.size() - i) - C(26 - (s[i] - 'a'), s.size() - i); } cout << sum + 1 << endl; rank--; } return 0; }