import java.text.DateFormat;
import java.util.Date;
import java.util.Locale;
/*有一个整数n,写一个函数f(n),返回0到n之间出现的"1"的个数。比如f(13)=6,现在f(1)=1,问有哪些n能满足f(n)=n？ 例如：f(13)=6, 因为1,2,3,4,5,6,7,8,9,10,11,12,13.数数1的个数，正好是6.*/
public class CountNumber {
public static void main(String[] args) {
Date now = new Date();
DateFormat fmt = DateFormat.getDateTimeInstance(DateFormat.SHORT, DateFormat.SHORT, Locale.CHINA);
String time =fmt.format(now);
System.out.println(time);
System.out.println(CountNumber.countOne(1111111111));
now = new Date();
time =fmt.format(now);
System.out.println(time);
}
/*计算单1个个数的方法*/
public static int countOne(int number){
int countone = 0; //记录单个1的数组
if(number <= 0){ //不合理情况，去掉
return -1;
}else if(number<=9){ //个位数，肯定有有且只有一个
return 1;
}else if(number==10){ //特殊情况2个
return 2;
}else{ //正常情况，从11开始计数
for(int i=11;i<=number;i++){
countone+=CountNumber.countANumber(i);
}
return countone+2;
}
} /*计算单个数1个数的函数*/
private static int countANumber(int number) {
int count=0; //计数器
int flag = 1; //用作检测数
while((number-flag)>=0){
if((number-flag)%(flag*10)==0){
count++;
}
flag = flag*10;
number = number-number%flag;
}
return count;
}
}以前在论坛上面看到的编程之美的题目。结果我按自己写的方法写了一个方法，结果发觉速度好慢。难道全部用基本类型，速度反而会慢？
public class Demo{
public int countOne(int max){
int count=0; //用来计数
for(int i=1;i<=max;i++){
char[] c=String.valueOf(i).toCharArray(); //把每个数都拆成一个字符数组
for(int j=0;j<c.length;j++){
if(c[j]=='1') //检查这个数组中含有'1'的个数
count++;
}
}
return count;
}
public static void main(String[] args){
int n=new Demo().countOne(13);
System.out.println(n); //结果是：6
}
}
public void countOne(int max){ //计算并输出从1到max中，所有满足countOne(n)=n的数
int count=0; //用来计数
for(int i=1;i<=max;i++){
char[] c=String.valueOf(i).toCharArray(); //把每个数都拆成一个字符数组
for(int j=0;j<c.length;j++){
if(c[j]=='1') //检查这个数组中含有'1'的个数
count++;
}
if(count==i)
System.out.println(i);
count=0; //还原count,准备检测下一个数
}
}
public static void main(String[] args){
new Demo().countOne(13); //结果：1
}
}
具体有哪些数是满足条件的，还没有作进一步的测试，好像这样的数很少
/**
*
*/
package test;/**
* @author - yy
* @time - Dec 1, 2008 9:30:40 AM
*/
public class Demo {
public int count1(int max) { // 2楼的程序
int count = 0; //用来计数
for (int i = 1; i <= max; i++) {
char[] c = String.valueOf(i).toCharArray(); //把每个数都拆成一个字符数组
for (int j = 0; j < c.length; j++) {
if (c[j] == '1') //检查这个数组中含有'1'的个数
count++;
}
}
return count;
}
public int countLess_1e2(int max) {
if (max == 0) {
return 0;
}
int count = 0;
int quotient = max / 10;
int remainder = max % 10;
switch (quotient) {
case 1:
if (remainder == 0) {
count = 2;
} else {
count = 3 + remainder;
}
break;
case 0:
count = 1;
break;
default:
if (remainder == 0) {
count = 10 + quotient;
} else {
count = 11 + quotient;
}
break;
}
return count;
}
public int countLess_1e3(int max) {
int count = 0;
int quotient = max / 100;
int remainder = max % 100;
switch (quotient) {
case 1:
if (remainder == 0) {
count = 21;
} else {
count = 21 + remainder + this.countLess_1e2(remainder);
}
break;
case 0:
count = this.countLess_1e2(remainder);
break;
default:
count = 100 + quotient * 20 + this.countLess_1e2(remainder);
break;
}
return count;
}
public int countLess_1e4(int max) {
int count = 0;
int quotient = max / 1000;
int remainder = max % 1000;
switch (quotient) {
case 1:
if (remainder == 0) {
count = 301;
} else {
count = 301 + remainder + this.countLess_1e3(remainder);
}
break;
case 0:
count = this.countLess_1e3(remainder);
break;
default:
count = 1000 + quotient * 300 + this.countLess_1e3(remainder);
break;
}
return count;
}
public int countLess_1e5(int max) {
int count = 0;
int quotient = max / 10000;
int remainder = max % 10000;
switch (quotient) {
case 1:
if (remainder == 0) {
count = 4001;
} else {
count = 4001 + remainder + this.countLess_1e4(remainder);
}
break;
case 0:
count = this.countLess_1e4(remainder);
break;
default:
count = 10000 + quotient * 4000 + this.countLess_1e4(remainder);
break;
}
return count;
}
public int countLess_1e6(int max) {
int count = 0;
int quotient = max / 100000;
int remainder = max % 100000;
switch (quotient) {
case 1:
if (remainder == 0) {
count = 50001;
} else {
count = 50001 + remainder + this.countLess_1e5(remainder);
}
break;
case 0:
count = this.countLess_1e5(remainder);
break;
default:
count = 100000 + quotient * 50000 + this.countLess_1e5(remainder);
break;
}
return count;
}
public int countLess_1e7(int max) {
int count = 0;
int quotient = max / 1000000;
int remainder = max % 1000000;
switch (quotient) {
case 1:
if (remainder == 0) {
count = 600001;
} else {
count = 600001 + remainder + this.countLess_1e6(remainder);
}
break;
case 0:
count = this.countLess_1e6(remainder);
break;
default:
count = 1000000 + quotient * 600000 + this.countLess_1e6(remainder);
break;
}
return count;
}
public int countLess_1e8(int max) {
int count = 0;
int quotient = max / 10000000;
int remainder = max % 10000000;
switch (quotient) {
case 1:
if (remainder == 0) {
count = 7000001;
} else {
count = 7000001 + remainder + this.countLess_1e7(remainder);
}
break;
case 0:
count = this.countLess_1e7(remainder);
break;
default:
count = 10000000 + quotient * 7000000 + this.countLess_1e7(remainder);
break;
}
return count;
}
public int countLess_1e9(int max) {
int count = 0;
int quotient = max / 100000000;
int remainder = max % 100000000;
switch (quotient) {
case 1:
if (remainder == 0) {
count = 80000001;
} else {
count = 80000001 + remainder + this.countLess_1e8(remainder);
}
break;
case 0:
count = this.countLess_1e8(remainder);
break;
default:
count = 100000000 + quotient * 80000000 + this.countLess_1e8(remainder);
break;
}
return count;
}
public int countLess_1e10(int max) {
int count = 0;
int quotient = max / 1000000000;
int remainder = max % 1000000000;
switch (quotient) {
case 1:
if (remainder == 0) {
count = 90000001;
} else {
count = 90000001 + remainder + this.countLess_1e9(remainder);
}
break;
case 0:
count = this.countLess_1e9(remainder);
break;
default:
count = 1000000000 + quotient * 90000000 + this.countLess_1e9(remainder);
break;
}
return count;
}
public static void main(String[] args) {
Demo demo = new Demo();
long s = System.currentTimeMillis();
System.out.println();
//System.out.println(demo.count1(Integer.MAX_VALUE)); 有谁验证一下结果
System.out.println(demo.countLess_1e10(Integer.MAX_VALUE));
System.out.println(Integer.MAX_VALUE);
System.out.println(System.currentTimeMillis() - s);
}
}
没看过编程之美,这是我总结采用数学归纳总结的,
看了10楼说得,特地下了编程之美看了看,
发现自己的效率比编程之美的还要高.
上面的算法我只测试到10^8,后面的没验证,因为后面的验证好慢,
我的算法几乎都是0毫秒,无论多大的数.
public static void main(String[] args) {
Demo demo = new Demo();
long start = System.currentTimeMillis();
//System.out.println(demo.countLess_1e10(100000000)); // 编程之美说要40多秒,我的几乎只要0毫秒
System.out.println(demo.countLess_1e10(1111111111));
long end = System.currentTimeMillis() ;
System.out.println("计算时间: "+(end - start)+" 毫秒");
// 输出结果是:
// 1111111120
// 计算时间: 0 毫秒
}
另外,测出了所有满足f(n)=n的数,共耗时8分22秒(502969毫秒) [cpu 2.0GHz,双核, 2G内存]
这是循环计算出来的
运行结果
for (int i = s; i < Integer.MAX_VALUE; i++) {
int n2 = demo.countLess_1e10(i);
if (i == n2) {
System.out.println(n2);
}
}
//输出满足的数:
// 0
// 1
// 199981
// 199982
// 199983
// 199984
// 199985
// 199986
// 199987
// 199988
// 199989
// 199990
// 200000
// 200001
// 1599981
// 1599982
// 1599983
// 1599984
// 1599985
// 1599986
// 1599987
// 1599988
// 1599989
// 1599990
// 2600000
// 2600001
// 13199998
// 35000000
// 35000001
// 35199981
// 35199982
// 35199983
// 35199984
// 35199985
// 35199986
// 35199987
// 35199988
// 35199989
// 35199990
// 35200000
// 35200001
// 117463825
// 500000000
// 500000001
// 500199981
// 500199982
// 500199983
// 500199984
// 500199985
// 500199986
// 500199987
// 500199988
// 500199989
// 500199990
// 500200000
// 500200001
// 501599981
// 501599982
// 501599983
// 501599984
// 501599985
// 501599986
// 501599987
// 501599988
// 501599989
// 501599990
// 502600000
// 502600001
// 513199998
// 535000000
// 535000001
// 535199981
// 535199982
// 535199983
// 535199984
// 535199985
// 535199986
// 535199987
// 535199988
// 535199989
// 535199990
// 535200000
// 535200001
// 1111111110
// 计算时间: 502969 毫秒