扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
下载作业帮安装包
扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
在十进制中0.9的n次方等于1吗？这里的0.9是指0.9循环.有哪位大数学家能给出正确的解答?噢,乖乖 n是指无穷大哎 不过，《在十进制中0．9的循环与1的大小有了结论 》说的有点道理
TC小简_堰杜
扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
为您推荐：
扫描下载二维码1454人阅读
算法学习笔记（13）
& 这个题目是群里贴出来的的，只有图片，题目如下：
解题思路：
很明显，这个题目如果直接计算11的n次方的值的话肯定不行，因为n的取值范围是0到1000，在C语言中即使用unsigned long也存储不了这么大的结果。
要解决这个问题，还是要从11这个数本身的特点入手。
我最开始的想法是展开（10+1）^n，然后从这个展开的式子中找到解题方法，但是展开的结果表示这个路子走不通，展开的结果中要计算阶乘，还要计算加法，这样的式子对解题来说没有帮助。
后来，就感觉这个每次乘以11的的结果比较特别，类似杨辉三角似的，所以在纸上开始手动计算11相乘的结果，发现了一个规律：假设现在的值为p（十进制表示），p乘以11的结果就是最低位仍为1，其他位都是p的相邻的两个数逐步相加的结果，当然最高位要做一下特殊处理，拿p的最高位加上进位（有可能两个数字相加的结果大于等于10），如下所示：
所以可以这样来解决这个问提：
1）申请两个长度为n（最终的值的十进制位个数不会超过n）的整数数组tmp，curr。tmp存储上个数的十进制表示，curr用来存储现在要计算的数的十进制表示。注意：数组中的每个元素存储的是十进制中的一位
2）循环遍历tmp、curr将各个元素初始化为-1.
3）因为要执行n次11相乘，所以外层循环的次数也是n，而内层循环的次数取决于上次的数的位数。循环计算当前数的值，也就是计算上个数乘以11的值
4）交换tmp、curr的值，然后检查是否执行完毕，否则重复执行第3步操作。
5）循环遍历tmp数组（因为3、4步骤中的循环结束时，tmp中存储的是最终的值），统计数组中1的个数，然后将结果返回
代码实现如下：
#include &stdio.h&
#include &ctype.h&
#include &stdlib.h&
void print_array(int *a, int n)
for (i = n-1; i &= 0; --i) {
printf(&%d&, a[i]);
printf(&\n&);
int solution(int n)
int *curr, *
int carry = 0;
int size = 2*n;
int count = 0;
curr = malloc(sizeof(int) * size);
if (!curr) {
printf(&Out of memory.\n&);
return -1;
tmp = malloc(sizeof(int) * size);
if (!tmp) {
free(curr);
printf(&Out of memory.\n&);
return -1;
for (i = 0; i & ++i) {
curr[i] = -1;
tmp[i] = -1;
tmp_len = 0;
for (i = 0; i & ++i) {
carry = 0;
curr[0] = 1;
for (j = 1; j & tmp_ ++j) {
curr[j] = tmp[j] + tmp[j - 1] +
carry = curr[j] / 10;
curr[j] = curr[j] % 10;
if (i & 0) {
curr[j] = tmp[j - 1] +
if (curr[j] &= 10) {
curr[j] = curr[j] % 10;
curr[++j] = 1;
tmp_len = ++j;
tmp_len = 1;
for (i = 0; i & ++i) {
printf(&%d&, tmp[i]);
if (tmp[i] == 1) {
printf(&\ncount = %d.\n&, count);
free(tmp);
free(curr);
int main(void)
solution(1000);
如果有什么错误，请帮忙指正，多谢！以免误人子弟.....
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：365108次
积分：4856
积分：4856
排名：第5587名
原创：114篇
评论：69条
(4)(1)(4)(3)(3)(7)(12)(6)(4)(9)(6)(8)(8)(18)(1)(2)(3)(12)(3)(1)(2)(1)找到11的n次方十进制表示中1的个数
这个题目是群里贴出来的的，只有图片，题目如下：
解题思路：很明显，这个题目如果直接计算11的n次方的#20540;的话肯定不行，因为n的取#20540;范围是0到1000，在C语言中即使用unsigned
long也存储不了这么大的结果。要解决这个问题，还是要从11这个数本身的特点入手。我最开始的想法是展开（10#43;1）^n，然后从这个展开的式子中找到解题方法，但是展开的结果表示这个路子走不通，展开的结果中要计算阶乘，还要计算加法，这样的式子对解题来说没有帮助。后来，就感觉这个每次乘以11的的结果比较特别，类#20284;杨辉三角#20284;的，所以在纸上开始手动计算11相乘的结果，发现了一个规律：假设现在的#20540;为p（十进制表示），p乘以11的结果就是最低位仍为1，其他位都是p的相邻的两个数逐步相加的结果，当然最高位要做一下特殊处理，拿p的最高位加上进位（有可能两个数字相加的结果大于等于10），如下所示：1
所以可以这样来解决这个问提：1）申请两个长度为n（最终的#20540;的十进制位个数不会超过n）的整数数组tmp，curr。tmp存储上个数的十进制表示，curr用来存储现在要计算的数的十进制表示。注意：数组中的每个元素存储的是十进制中的一位2）循环遍历tmp、curr将各个元素初始化为-1.3）因为要执行n次11相乘，所以外层循环的次数也是n，而内层循环的次数取决于上次的数的位数。循环计算当前数的#20540;，也就是计算上个数乘以11的#20540;4）交换tmp、curr的#20540;，然后检查是否执行完毕，否则重复执行第3步操作。5）循环遍历tmp数组（因为3、4步骤中的循环结束时，tmp中存储的是最终的#20540;），统计数组中1的个数，然后将结果返回代码实现如下：#include
#include #include void print_array(int *a, int n){ for (i =
n-1; i &= 0; --i) { printf("%d", a[i]); } printf("\n");}int
solution(int n){ int *curr, * int tmp_ int *p; int carry =
0; int i, int size = 2*n; int count = 0; curr =
malloc(sizeof(int) * size); if (!curr) { printf("Out of
memory.\n"); return -1; } tmp = malloc(sizeof(int) * size); if
(!tmp) { free(curr); printf("Out of memory.\n"); return -1; } for
(i = 0; i & i) { curr[i] = -1; tmp[i] = -1; } tmp_len = 0;
for (i = 0; i & i) { carry = 0; curr[0] = 1; for (j = 1; j
& tmp_ j) { curr[j] = tmp[j] tmp[j - 1] carry =
curr[j] / 10; curr[j] = curr[j] % 10; } if (i & 0) { curr[j] =
tmp[j - 1] if (curr[j] &= 10) { curr[j] = curr[j] % 10;
curr[ j] = 1; } tmp_len = } else { tmp_len = 1; } p = tmp =
curr = } for (i = 0; i & i) { printf("%d",
tmp[i]); if (tmp[i] == 1) { } } printf("\ncount = %d.\n",
count); free(tmp); free(curr); return 0;}int main(void){
solution(1000); return 0;}
如果有什么错误，请帮忙指针，多谢！以免误人子弟.....
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。algorithm（1）
转自 &http://blog.csdn.net/justlinux2010/article/details/8931677
这个题目是群里贴出来的的，只有图片，题目如下：
解题思路：
很明显，这个题目如果直接计算11的n次方的值的话肯定不行，因为n的取值范围是0到1000，在C语言中即使用unsigned long也存储不了这么大的结果。
要解决这个问题，还是要从11这个数本身的特点入手。
我最开始的想法是展开（10+1）^n，然后从这个展开的式子中找到解题方法，但是展开的结果表示这个路子走不通，展开的结果中要计算阶乘，还要计算加法，这样的式子对解题来说没有帮助。
后来，就感觉这个每次乘以11的的结果比较特别，类似杨辉三角似的，所以在纸上开始手动计算11相乘的结果，发现了一个规律：假设现在的值为p（十进制表示），p乘以11的结果就是最低位仍为1，其他位都是p的相邻的两个数逐步相加的结果，当然最高位要做一下特殊处理，拿p的最高位加上进位（有可能两个数字相加的结果大于等于10），如下所示：
所以可以这样来解决这个问提：
1）申请两个长度为n（最终的值的十进制位个数不会超过n）的整数数组tmp，curr。tmp存储上个数的十进制表示，curr用来存储现在要计算的数的十进制表示。注意：数组中的每个元素存储的是十进制中的一位
2）循环遍历tmp、curr将各个元素初始化为-1.
3）因为要执行n次11相乘，所以外层循环的次数也是n，而内层循环的次数取决于上次的数的位数。循环计算当前数的值，也就是计算上个数乘以11的值
4）交换tmp、curr的值，然后检查是否执行完毕，否则重复执行第3步操作。
5）循环遍历tmp数组（因为3、4步骤中的循环结束时，tmp中存储的是最终的值），统计数组中1的个数，然后将结果返回
代码实现如下：
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：47175次
排名：千里之外
转载：53篇
(1)(1)(1)(2)(2)(3)(1)(5)(8)(6)(3)(5)(6)(3)(3)(4)(7)2326人阅读
&&&&&& 给定一个十进制整数N,求出从1到N的所有整数中出现”1”的个数。&
&&&&& 例如：N=2，1,2出现了1个“1”。
&&&&&&&& && N=12，1,2,3,4,5,6,7,8,9,10,11,12。出现了5个“1”。
问题求解：
&&&&&& 最直接的方法就是从1开始遍历到N，将其中每一个数中含有“1”的个数加起来，就得到了问题的解。
&&&& &代码如下：
1 publiclong CountOne3(long n)
3 long i =<span style="color:#,j =<span style="color:#;
4 long count =<span style="color:#;
5 for (i =<span style="color:#; i &= i&#43;&#43;)
8 while (j !=<span style="color:#)
<span style="color:# if (j %<span style="color:#==<span style="color:#)
<span style="color:#
count&#43;&#43;;
<span style="color:#
j = j /<span style="color:#;
<span style="color:#
<span style="color:#
<span style="color:# return
<span style="color:#
&&&&&&& 此方法简单，容易理解，但它的问题是效率，时间复杂度为O（N * lgN），N比较大的时候，需要耗费很长的时间。
&&&&&&&& 我们重新分析下这个问题，对于任意一个个位数n，只要n&=1,它就包含一个“1”；n&1，即n=0时，则包含的“1”的个数为0。于是我们考虑用分治的思想将任意一个n位数不断缩小规模分解成许多个个位数，这样求解就很方便。
&&&&&&& 但是，我们该如何降低规模？仔细分析，我们会发现，任意一个n位数中“1”的个位可以分解为两个n-1位数中“1”的个数的和加上一个与最高位数相关的常数C。例如，f(12) = f(10 - 1) &#43; f(12 - 10) &#43; 3,其中3是表示最高位为1的数字个数，这里就是10,11,12；f(132)=f(100 -1) &#43; f(132 - 100) &#43; 33，33代表最高位为1的数字的个数，这里就是100~132；f(232) = 2*f(100 - 1) &#43; f(32) &#43; 100，因为232大于199，所以它包括了所有最高位为1的数字即100~199，共100个。
&&&&&&& 综上，我们分析得出，最后加的常数C只跟最高位n1是否为1有关，当最高位为1时，常数C为原数字N去掉最高位后剩下的数字&#43;1，当最高位为1时，常数C为10bit，其中bit为N的位数-1，如N=12时，bit=1，N=232时，bit=2。
&&&&&& 于是，我们可以列出递归方程如下：
&&&&&& if(n1 == 1)
&&&&&&&&&& f(n) = f(10bit-1) &#43; f(n - 10bit)& &#43; n - 10bit&#43; 1;
&&&&&& else
&&&&&&&&&& f(n) = n1*f(10bit-1) &#43; f(n – n1*10bit) &#43; 10bit;
&&&&&& 递归的出口条件为：
&&&&&& if(1&n&10)& return 1;
&&&&& &else if (n == 0) return 0;
&&&&&& 基于此，编写如下代码：
1 publiclong CountOne(long n)
3 long count =<span style="color:#;
4 if (n ==<span style="color:#)
count =<span style="color:#;
6 elseif (n &<span style="color:#&& n &<span style="color:#)
count =<span style="color:#;
<span style="color:# long highest =//表示最高位的数字
<span style="color:# &int bit =<span style="color:#;
<span style="color:# while (highest &=<span style="color:#)
<span style="color:#
<span style="color:#
highest = highest /<span style="color:#;
<span style="color:#
bit&#43;&#43;;
<span style="color:#
<span style="color:#
<span style="color:# int weight = (int)Math.Pow(<span style="color:#, bit);//代表最高位的权重，即最高位一个1代表的大小
<span style="color:# &if (highest ==<span style="color:#)
<span style="color:#
<span style="color:#
count = CountOne(weight -<span style="color:#)
<span style="color:# &#43; CountOne(n - weight)
<span style="color:# &#43; n - weight &#43;<span style="color:#;
<span style="color:#
<span style="color:# else
<span style="color:#
<span style="color:#
count = highest * CountOne(weight -<span style="color:#)
<span style="color:# &#43; CountOne(n - highest * weight)
<span style="color:# &#43;
<span style="color:#
<span style="color:#
<span style="color:# return
<span style="color:#
&&&&&&& &此算法的优点是不用遍历1~N就可以得到f(N)。经过我测试，此算法的运算速度比解法一快了许多许多，数字在1010内时，算法都可以在毫秒级内结束，而解法一在计算109时，时间超过了5分钟。但此算法有一个显著的缺点就是当数字超过1010时会导致堆栈溢出，无法计算。
&&&&&&& 还有就是，我尝试了许久也没有计算出此算法的时间复杂度到底是多少，&#20284;乎是O（lg2N），我并不确定，希望知道的高手能给予解答。
&&&&&&& &解法二告诉我们1~ N中“1”的个数跟最高位有关，那我们换个角度思考，给定一个N，我们分析1~N中的数在每一位上出现1的次数的和，看看每一位上“1”出现的个数的和由什么决定。
&&&&&& <span style="color:#位数的情况：
&&&&&& 在解法二中已经分析过，大于等于1的时候，有1个，小于1就没有。
&&&&&& <span style="color:#位数的情况：
&&&&&& N=13,个位数出现的1的次数为2，分别为1和11，十位数出现1的次数为4，分别为10,11,12,13，所以f(N) = 2&#43;4。
&&&&&& N=23,个位数出现的1的次数为3，分别为1，11，21，十位数出现1的次数为10，分别为10~19，f(N)=3&#43;10。
&&&&&& 由此我们发现，个位数出现1的次数不仅和个位数有关，和十位数也有关，如果个位数大于等于1，则个位数出现1的次数为十位数的数字加1；如果个位数为0，个位数出现1的次数等于十位数数字。而十位数上出现1的次数也不仅和十位数相关，也和个位数相关：如果十位数字等于1，则十位数上出现1的次数为个位数的数字加1，假如十位数大于1，则十位数上出现1的次数为10。
&&&&&& <span style="color:#位数的情况:
&&&&&& N=123
&&&&&& 个位出现1的个数为13:1,11,21，…，91,101,111,121
&&&&&& 十位出现1的个数为20:10~19,110~119
&&&&&& 百位出现1的个数为24:100~123
&&&&&& 我们可以继续分析4位数，5位数，推导出下面一般情况：&
&&&&&& 假设N，我们要计算百位上出现1的次数，将由三部分决定：百位上的数字，百位以上的数字，百位一下的数字。
&&&&&& 如果百位上的数字为0，则百位上出现1的次数仅由更高位决定，比如12013，百位出现1的情况为100~199,00~2199，…，，共1200个。等于更高位数字乘以当前位数，即12 * 100。
&&&&&& 如果百位上的数字大于1，则百位上出现1的次数仅由更高位决定，比如12213，百位出现1的情况为100~199,00~2199，…，，共1300个。等于更高位数字加1乘以当前位数，即（12 &#43; 1）*100。
&&&&&&& 如果百位上的数字为1，则百位上出现1的次数不仅受更高位影响，还受低位影响。例如12113，受高位影响出现1的情况：100~199,00~2199，…，，共1200个，但它还受低位影响，出现1的情况是，共114个，等于低位数字113&#43;1。
&&&&&& 综合以上分析，写出如下代码：
1 publiclong CountOne2(long n)
3 long count =<span style="color:#;
4 long i =<span style="color:#;
5 long current =<span style="color:#,after =<span style="color:#,before =<span style="color:#;
6 while((n / i) !=<span style="color:#)
current = (n / i) %<span style="color:#;
before = n / (i *<span style="color:#);
<span style="color:#
after = n - (n / i) *
<span style="color:#
<span style="color:# if (current &<span style="color:#)
<span style="color:#
count = count &#43; (before &#43;<span style="color:#) *
<span style="color:# elseif (current ==<span style="color:#)
<span style="color:#
count = count &#43; before *
<span style="color:# elseif(current ==<span style="color:#)
<span style="color:#
count = count &#43; before * i &#43; after &#43;<span style="color:#;
<span style="color:#
<span style="color:#
i = i *<span style="color:#;
<span style="color:#
<span style="color:# return
<span style="color:#
<span style="color:#
&&&& 此算法的时间复杂度仅为O(lgN)，且没有递归保存现场的消耗和堆栈溢出的问题。
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：188212次
积分：2833
积分：2833
排名：第11931名
原创：88篇
转载：50篇
评论：38条
(2)(1)(3)(1)(2)(7)(6)(7)(3)(11)(18)(8)(1)(4)(6)(24)(27)(7)