java 方法,利用到stringbuffer,将数字当做char来看.例如 1,2,3,4,,,,12 则 生成StringBuffer 123456789101112.之后就好说了,,,, 具体函数如下: public int f(int n){ int c=0; StringBuffer sb=new StringBuffer(); for(int j=1;j<=n;j++) { sb.append(j); } int length=sb.length(); String yi=null; for(int k=0;k<length;k++){ yi=String.valueOf(sb.charAt(k)); if("1".equals(yi)){ c++; } }
return c;
}经过测试10000之内的 只有满足.....估计再大的数据 我这小机器就跑不动了
楼上最后丢字了 10000之内只有1满足 n=f(n)
package net.csdn.community;public class Test { public static int ccccc(int num, int tens, int a) { if (tens == 0) return 0; int ak = num / tens; if (ak > a) { return tens + ccccc(num % tens, tens / 10, a) + ak * ccccc(tens - 1, tens / 10, a); } else if (ak == a) { return num % tens + 1 + ak * ccccc(tens - 1, tens / 10, a) + ccccc(num % tens, tens / 10, a); } else { return ccccc(num % tens, tens / 10, a) + ak * ccccc(tens - 1, tens / 10, a); } }
public static void main(String[] args) { System.out.println(ccccc(200, 100, 1));
一个改进的思路： 对于N=10^n-1 (0、9、99、999……)来说 设F(n)=f(10^n-1) F(n)=A(n)+B(n) A(n)表示由最高位带来的1的个数 B(n)表示由非最高位带来的1的个数 那么，易得A(n)=10^n， B(n)=10*F(n-1) (n>0) B(0)=0 综上所述，F(n)=F(n-1)+10^n=n*10^(n-1)而对任意正整数N=a*10^n+b 其中a为N的最高位数(1-9) 那么，f(N)中由最高位带来的1的个数C(N)=a>1 ? 10^n : b+1 而非最高位来带的1的个数D(N)=f(b)+a*F(n) 其中f(b)为[a*10^n,a*10^n+b]中的个数 aF(n)为[0,a*10^n]中的个数所以，f(N)=f(b)+aF(n)+(a>1 ? 10^n : b+1) =f(b)+an*10^(n-1) + (a>1 ? 10^n : b+1)应该还能进一步归纳到O(1)复杂度，不过这里就懒得归纳了java代码：public class GoogleTest { private static final int[] tenSqr = new int[]{1, 10, 100, 1000, 10000, 100000, 1000000, 10000000}; // 获取a的位数 private static int get_n(int a){ int n = 0; while (tenSqr[n] <= a) n++; return n-1; } private static int f(int N){ if (N == 0) return 0; else if (N < 10) return 1; int n = get_n(N); int a = N / tenSqr[n]; int b = N % tenSqr[n]; return f(b) + a * n * tenSqr[n-1] + (a > 1 ? tenSqr[n] : b+1); } public static void main(String[] args) { // TODO Auto-generated method stub for (int i = 1; i < 1000; ++i){ System.out.println("f(" + i + ")=" + f(i)); } } }
import java.util.regex.Matcher; import java.util.regex.Pattern;public class GoogleFace { static int imatch = 0; static public void F(int x) { String y = ""; String f = ""; imatch = 0; for (int i =1;i<=x;i++) { f = String.valueOf(x); y = Integer.toString(i);
//生成Pattern对象并且编译一个简单的正则表达式(变量f) Pattern p = Pattern.compile(f);
//用Pattern类的matcher()方法生成一个Matcher对象 Matcher m = p.matcher(y);
//使用find()方法查找第一个匹配的对象 boolean result = m.find(); while(result) { imatch++; //继续查找下一个匹配对象 result = m.find(); }
if (imatch == x) { System.out.println("F("+x+")="+imatch); } } }
public static void main(String[] args) { for(int i = 1;i<=10000;i++) { F(i); } }}
package com.bruceeckel.c12;import java.util.regex.Matcher; import java.util.regex.Pattern;public class GoogleFace { static int imatch = 0; static public void F(int x) { String y = ""; String f = ""; imatch = 0; for (int i =1;i<=x;i++) { f = String.valueOf(x); y = Integer.toString(i);
//生成Pattern对象并且编译一个简单的正则表达式(变量f) Pattern p = Pattern.compile(f);
//用Pattern类的matcher()方法生成一个Matcher对象 Matcher m = p.matcher(y);
//使用find()方法查找第一个匹配的对象 boolean result = m.find(); while(result) { imatch++; //继续查找下一个匹配对象 result = m.find(); } }
//如果匹配，则打印 if (imatch == x) { System.out.println("F("+x+")="+imatch); } }
public static void main(String[] args) { for(int i = 1;i<=10000;i++) { F(i); } }}
上面的太复杂了：/* 有一个整数n,写一个函数f(n), 返回0到n之间出现的"1"的个数。 比如f(13)=6,现在f(1)=1,问有哪些n能满足f(n)=n？ */ int GetOneCount(int nNum) { int i = 0; int nCount = 0;
do { if( i < 10 ) { if ( i == 1 ) { ++nCount; } } else { nCount += GetOneOfNum(i); } ++i; }while( i <= nNum ); return nCount; }/* 功能：数字转化为字符，并返回是'1'的个数 */ int GetOneOfNum(int nNum) { int nCnt = 0; do { if ( 1 == nNum % 10 ) { ++nCnt; } } while ( nNum = nNum / 10 ); return nCnt; }
1. #include "stdafx.h"
2.
3. #include <windows.h>
4. #include <stdlib.h>
5.
6. int f(int n);
7. int count1(int n);
8. int cal(unsigned int number,int nwei,int count1,unsigned int ncount);
9.
10. int gTable[10];
11. const unsigned int gMAX = 4000000000L;
12.
13. int main(int argc, char* argv[])
14. {
15. int i;
16. unsigned int n=1;
17. unsigned int ncount = 0;
18. int nwei = 0;
19. int ncount1;
20.
21. /*if(argc>1)
22. {
23. n = atoi(argv[1]);
24. ncount = f(n);
25. printf("f(%d) = %d\n",n,ncount);
26. }*/
27.
28. int beginTime=GetTickCount();
29. //init gTable
30. for(i=0;i<10;++i)
31. {
32. n *= 10;
33. gTable[i] = f(n-1);
34. }
35.
36. n=0;
37. nwei = 0;
38. ncount1 = 0;
39. while(n<gMAX)
40. {
41. unsigned int temp;
42.
43. temp = 1;
44.
45. ncount =cal(n,nwei,ncount1,ncount);
46. for(i=0;i<nwei;++i)
47. temp *= 10;
48. n += temp;
49. if( (n/temp)/10 == 1)
50. ++nwei;
51. ncount1 = count1(n);
52. }
53.
54. int endTime=GetTickCount();
55. endTime-=beginTime;
56.
57. printf("time: %d ms\n",endTime);
58. return 0;
59. }
60.
61.
62. int f(int n)
63. {
64. int ret = 0;
65. int ntemp=n;
66. int ntemp2=1;
67. int i=1;
68. while(ntemp)
69. {
70. ret += (((ntemp-1)/10)+1) * i;
71. if( (ntemp%10) == 1 )
72. {
73. ret -= i;
74. ret += ntemp2;
75. }
76. ntemp = ntemp/10;
77. i*=10;
78. ntemp2 = n%i+1;
79. }
80. return ret;
81. }
82.
83. int count1(int n)
84. {
85. int count = 0;
86. while(n)
87. {
88. if( (n%10) == 1)
89. ++count;
90. n /= 10;
91. }
92. return count;
93. }
94.
95. int cal(unsigned int number,int nwei,int count1,unsigned int ncount)
96. {
97. int i,n=1;
98. unsigned int maxcount;
99. if(nwei==0)
100. {
101. ncount += count1;
102. if(number == ncount)
103. {
104. printf("f(%d) = %d \n",number,number);
105. }
106. return ncount;
107. }
108. for(i=0;i<nwei;++i)
109. n *= 10;
110. maxcount = ncount + gTable[nwei-1];
111. maxcount += count1*n;
112. if(ncount > (number + (n-1)) )
113. {
114. return maxcount;
115. }
116. if(maxcount < number)
117. {
118. return maxcount;
119. }
120. n /= 10;
121. for(i=0;i<10;++i)
122. {
123. if(i==1)
124. ncount = cal(number+i*n,nwei-1,count1+1,ncount);
125. else
126. ncount = cal(number+i*n,nwei-1,count1,ncount);
127. }
128. return ncount;
129. }
生成StringBuffer 123456789101112.之后就好说了,,,, 具体函数如下:
public int f(int n){
int c=0;
StringBuffer sb=new StringBuffer();
for(int j=1;j<=n;j++)
{
sb.append(j);
}
int length=sb.length();
String yi=null;
for(int k=0;k<length;k++){
yi=String.valueOf(sb.charAt(k));
if("1".equals(yi)){
c++;
}
}
return c;
}经过测试10000之内的 只有满足.....估计再大的数据 我这小机器就跑不动了
package net.csdn.community;public class Test {
public static int ccccc(int num, int tens, int a) {
if (tens == 0) return 0;
int ak = num / tens;
if (ak > a) {
return tens + ccccc(num % tens, tens / 10, a) + ak * ccccc(tens - 1, tens / 10, a);
}
else
if (ak == a) {
return num % tens + 1 + ak * ccccc(tens - 1, tens / 10, a) + ccccc(num % tens, tens / 10, a);
}
else {
return ccccc(num % tens, tens / 10, a) + ak * ccccc(tens - 1, tens / 10, a);
}
}
public static void main(String[] args) {
System.out.println(ccccc(200, 100, 1));
}}
之前有人問過了...num就是你的n,tens是num的長度,就是個位是1,十位是10,so forth...a是0至9,你這里的情況是1
对于N=10^n-1 (0、9、99、999……)来说
设F(n)=f(10^n-1)
F(n)=A(n)+B(n)
A(n)表示由最高位带来的1的个数
B(n)表示由非最高位带来的1的个数
那么，易得A(n)=10^n，
B(n)=10*F(n-1) (n>0)
B(0)=0
综上所述，F(n)=F(n-1)+10^n=n*10^(n-1)而对任意正整数N=a*10^n+b
其中a为N的最高位数(1-9)
那么，f(N)中由最高位带来的1的个数C(N)=a>1 ? 10^n : b+1
而非最高位来带的1的个数D(N)=f(b)+a*F(n)
其中f(b)为[a*10^n,a*10^n+b]中的个数
aF(n)为[0,a*10^n]中的个数所以，f(N)=f(b)+aF(n)+(a>1 ? 10^n : b+1)
=f(b)+an*10^(n-1) + (a>1 ? 10^n : b+1)应该还能进一步归纳到O(1)复杂度，不过这里就懒得归纳了java代码：public class GoogleTest { private static final int[] tenSqr
= new int[]{1, 10, 100, 1000, 10000, 100000, 1000000, 10000000};
// 获取a的位数
private static int get_n(int a){
int n = 0;
while (tenSqr[n] <= a) n++;
return n-1;
}
private static int f(int N){
if (N == 0) return 0;
else if (N < 10) return 1;
int n = get_n(N);
int a = N / tenSqr[n];
int b = N % tenSqr[n];
return f(b) + a * n * tenSqr[n-1] + (a > 1 ? tenSqr[n] : b+1);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
for (int i = 1; i < 1000; ++i){
System.out.println("f(" + i + ")=" + f(i));
}
}
}
import java.util.regex.Pattern;public class GoogleFace
{
static int imatch = 0;
static public void F(int x)
{
String y = "";
String f = "";
imatch = 0;
for (int i =1;i<=x;i++)
{
f = String.valueOf(x);
y = Integer.toString(i);
//生成Pattern对象并且编译一个简单的正则表达式(变量f)
Pattern p = Pattern.compile(f);
//用Pattern类的matcher()方法生成一个Matcher对象
Matcher m = p.matcher(y);
//使用find()方法查找第一个匹配的对象
boolean result = m.find();
while(result)
{
imatch++;
//继续查找下一个匹配对象
result = m.find();
}
if (imatch == x)
{
System.out.println("F("+x+")="+imatch);
}
}
}
public static void main(String[] args)
{
for(int i = 1;i<=10000;i++)
{
F(i);
}
}}
import java.util.regex.Pattern;public class GoogleFace
{
static int imatch = 0;
static public void F(int x)
{
String y = "";
String f = "";
imatch = 0;
for (int i =1;i<=x;i++)
{
f = String.valueOf(x);
y = Integer.toString(i);
//生成Pattern对象并且编译一个简单的正则表达式(变量f)
Pattern p = Pattern.compile(f);
//用Pattern类的matcher()方法生成一个Matcher对象
Matcher m = p.matcher(y);
//使用find()方法查找第一个匹配的对象
boolean result = m.find();
while(result)
{
imatch++;
//继续查找下一个匹配对象
result = m.find();
}
}
//如果匹配，则打印
if (imatch == x)
{
System.out.println("F("+x+")="+imatch);
}
}
public static void main(String[] args)
{
for(int i = 1;i<=10000;i++)
{
F(i);
}
}}
有一个整数n,写一个函数f(n),
返回0到n之间出现的"1"的个数。
比如f(13)=6,现在f(1)=1,问有哪些n能满足f(n)=n？
*/
int GetOneCount(int nNum)
{
int i = 0; int nCount = 0;
do
{
if( i < 10 )
{
if ( i == 1 )
{
++nCount;
}
}
else
{
nCount += GetOneOfNum(i);
}
++i;
}while( i <= nNum ); return nCount;
}/*
功能：数字转化为字符，并返回是'1'的个数
*/
int GetOneOfNum(int nNum)
{
int nCnt = 0;
do
{
if ( 1 == nNum % 10 )
{
++nCnt;
}
} while ( nNum = nNum / 10 ); return nCnt;
}
# 这样的话，每100 个数之间会有20个1
# 但是 100 ～ 199 是个特例，这中间除了这20个1 还有100个百位开头的1 这和10～19 其实是差不多的
# 其实昨天算错了，不应该算 0～100 是多少 应该算 0～99 为多少，凡是1作为首位的 都需要特殊处理0~9 之间有1 个 个位1 ，10～19之间也有1个 个位1 也就是说 每10位中有1位个位1 (当个位大于1时也会有1个个位1)
# 0~99之间有 1类10位1(10~19) 每百位有一位10位1
# 同理，每千位有1位 百位1
# 可能有点乱，没事 找个实例实验一下 253怎么样？呵呵
#
# 按照上面的分析，253 拆分如下 m为总数：
# 有25 + 1(这里加1 因为3>1)个 个位1 (01,11,21……251) || m=26
# 有2 + 1(这里加1 因为 5>1)个 十位1 (1*,11*,21*) || m=26 + 3*10 =56
# 有1(因为 2>1)个百位1 (1**) || m=56 + 1*100 = 156
#
# 呵呵 这样就出来了 程序就好写了 但是为1的时候要特殊处理下 将后面所有的数+1(因为是 00～53) 算做1的数量 比如 153
# m = 16 + 2*10 + (53+1) = 90 这个结果对吧。