package org.shaoxinglay.algorithm;
import java.math.BigInteger;
/**
* 问题:有一个整数n,写一个函数f(n),返回0到n之间出现的"1"的个数。 比如f(13)=6,现在f(1)=1,问此后最大的f(n)=n的n是什么?<br/>
* 本类提供3种不同实现算f(n)的方法,理论上能处理趋于无穷大的整数,只要计算机内存足够大,而不限于Java的整型、长整型。
*
*/
public class Demo {
/**
* 基于字符串实现的算f(n),原理最通俗易懂,但同时效率较为低下。不宜处理大数。
*
* @param n
* 自变量n的值
* @param target
* 目标数字(0 <= target < 10)
* @return f(n)的值
*/
public static int execByString(int n, int target) {
checkTarget(target);
int count = 0;
char targ = (target + "").charAt(0);
String s = null;
for (int i = 0; i <= n; i++) {
s = "" + i;
for (int j = 0; j < s.length(); j++) {
if (s.charAt(j) == targ) {
count++;
}
}
}
return count;
}
/**
* 与使用字符串处理一样,使用迭代的方式进行处理,时间复杂度可认为是O(n·log<sub>10</sub>n)。<br />
* 欲求f(n),必要先求f(n-1),因此效率其实不高,处理大数也是力不从心啊。
*
* @param n
* 自变量n的值
* @param target
* 目标数字(0 <= target < 10)
* @return f(n)的值
*/
public static long execByIterate(int n, int target) {
checkTarget(target);
long count;
int num, temp;
count = num = temp = 0;
while (num <= n) {
temp = num;
while (temp != 0) {
if (temp % 10 == target)
count++;
temp /= 10;
}
num++;
}
if (target == 0) {
count++; // 把初始的0补上
}
return count;
}
/**
* 使用排列组合的方式进行处理,能把时间复杂度降到O(log<sub>10</sub>n),因此,本方法处理Long.MAX_VALUE也毫无鸭梨!
*
* @param n
* 自变量n的值
* @param target
* 目标数字(0 <= target < 10)
* @return BigInteger表示的f(n)
*/
public static BigInteger execByPermutation(long n, int target) {
checkTarget(target);
int[] nums = getArray(n);
int len = nums.length;
BigInteger count = new BigInteger("0");
BigInteger powbase = new BigInteger("10");
long left, right;
for (int i = 0; i < len; i++) {
right = (long) Math.pow(10, (len - i - 1));
if (target != 0) {
left = (long) (n / Math.pow(10, len - i));
if (nums[i] > (target - 1)) {
left++;
}
} else {
left = (long) (n / Math.pow(10, len - i));
if (left > 0) {
left = left - (long) Math.pow(10, i - 1) + 1;
}
}
count = count.add(BigInteger.valueOf(right * left));
if (nums[i] == target) {
long temp = (long) Math.pow(10, (len - i - 1));
long sub = temp - ((long) (n % temp)) - 1;
count = count.subtract(BigInteger.valueOf(sub));
}
}
if (target == 0) {
count = zeroCompensate(len, count, powbase);
}
return count;
}
/**
* 使用排列组合的方式进行处理,能把时间复杂度降到O(log<sub>10</sub>n),因此,本方法处理再大的数也无鸭梨!
*
* @param n
* String类型,一个整数的字符串表示,例如:5236521452145 表示为"5236521452145" <br>
* 注意:只能是十进制的表示法
* @param target
* 目标数字(0 <= target < 10)
* @return BigInteger表示的f(n)
*/
public static BigInteger execByPermutation(String n, int target) {
checkTarget(target);
BigInteger src = new BigInteger(n);
String nstr = src.toString();
int[] nums = new int[nstr.length()];
for (int i = 0; i < nums.length; i++) {
nums[i] = Integer.parseInt(nstr.charAt(i) + "");
}
int len = nums.length;
BigInteger count = BigInteger.ZERO;
BigInteger powbase = BigInteger.TEN;
BigInteger left = BigInteger.ZERO;
BigInteger right = BigInteger.ZERO;
for (int i = 0; i < len; i++) {
right = powbase.pow(len - i - 1);
if (target != 0) {
left = src.divide(powbase.pow(len - i));
if (nums[i] > (target - 1)) {
left = left.add(BigInteger.ONE);
}
} else {
left = src.divide(powbase.pow(len - i));
if (i > 0) {
left = left.subtract(powbase.pow(i - 1))
.add(BigInteger.ONE);
}
}
count = count.add(right.multiply(left));
if (nums[i] == target) {
BigInteger temp = powbase.pow(len - i - 1);
BigInteger sub = temp.subtract(src.mod(temp)).subtract(
BigInteger.ONE);
count = count.subtract(sub);
}
}
if (target == 0) {
count = zeroCompensate(len, count, powbase);
}
return count;
}
private static BigInteger zeroCompensate(int len, BigInteger count,
BigInteger powbase) {
int bl = len - 2;
if (bl < 1) {
count = count.add(BigInteger.valueOf(1));
} else if (bl == 1) {
count = count.add(BigInteger.valueOf(10));
} else {
BigInteger bigI = BigInteger.valueOf(0);
for (int i = 1; i < bl; i++) {
bigI = bigI.add(powbase.pow(i));
}
BigInteger bc = BigInteger.valueOf(bl).multiply(powbase.pow(bl))
.subtract(bigI);
count = count.add(bc);
}
return count;
}
/**
* 如果目标数字没在0-9中抛出非法参数异常
*
* @param target
* 目标数字
* @throws IllegalArgumentException
*/
private static void checkTarget(int target) throws IllegalArgumentException {
if (target < 0 || target > 9) {
throw new IllegalArgumentException("目标数字" + target + "不在0 - 9中");
}
}
private final static long[] sizeTable = { 9, 99, 999, 9999, 99999, 999999,
9999999, 99999999, 999999999, 9999999999L, 99999999999L,
999999999999L, 9999999999999L, 99999999999999L, 999999999999999L,
9999999999999999L, 99999999999999999L, 999999999999999999L,
Long.MAX_VALUE };
private static int sizeOfLong(long x) {
for (int i = 0;; i++)
if (x <= sizeTable[i])
return i + 1;
}
private static int[] getArray(long n) {
int len = sizeOfLong(n);
int[] result = new int[len];
int i = len - 1;
while (i >= 0) {
result[i--] = (int) (n % 10);
n = n / 10;
}
return result;
}
}
对于f(n)=n,最大的n值是多少,可证明n是确定的,原理是当n大于某一数值时,f(n)恒大于n。
分享到:
相关推荐
有一个整数n,写一个函数f(n),返回0到n之间出现的 "1 "的个数。比如f(13)=6,现在f(1)=1,问下一个最大的f(n)=n的n是什么?
【题目】将一个m位(m>1)的正整数n,依次去掉n中的某一位数字,得到m个整数,并将这m个整数按从小到大的次序排列后输出。 例如,对于整数387,依次去掉其中一位后,得到三个数:87、37、38,排序后为:37、38、87...
C语言程序设计-编写函数判断一个整数能否同时被3和5整除,若能则返回值为1,否则为0;调用该函数求出15~300之间能同时被3和5整除的数的个数;.c
从键盘任意输入两个整数,输出两数之间的素数,素数判断用函数实现。 扩展要求:1)程序可以循环执行,判断完一组可以再进行下一组;可以设定一个特殊键退出 2) 当输入的两个数不是大于2,则重新输入 3)输入的数...
C语言程序设计-编写main程序调用函数fact求解从m个元素选n个元素的组合数的个数;计算公式是: 组合数=m!(n!.(m-n)!);要求m不能小于n,否则应有容错处理;说明:函数fact(x)的功能是求x!;
C++计算一个数字的二进制中0或1的个数原理及代码
C语言程序设计-求大于lim(lim小于100的整数)并且小于100的所有素数并放在aa数组中,该函数返回所求出素数的个数
8.7写一函数,输入一个4位数字,要求输出这4个数字字符,但每两个数字之间有一个空格。如输入1990,应输出”1 9 9 0”。 52 8.8编写一函数,有实参传来一个字符串,统计此字符串中字母,数字,空格和其它字符的个数...
输入一个正整数n (1<n),再输入n 个整数,输出最大值极其下标(设最大值惟一,下标从0 开始)。 输入一个正整数n (1<n),再输入n 个整数,将最小值与第一个数交换,最大值与最后一个数交换,然后输出交换后的n 个数...
2.请编写函数fun,它的功能是:求出1到1000之内能被7或11整除、但不能同时被7和11整除的所有整数并将它们放在a所指的数组中,通过n返回这些数的个数。_请编写函数fun,它的功能是 求出 1 到 1000 之间能被 7 或11...
c++1)一个包含10个元素的数组,已按升序排序,输入一个任意的整数, 将该整数插入数组中,使数组元素仍保持升序排列。要求编写一个通用的 插入排序函数InsertSort,它带有三个参数,第一个参数是含有n个元素的数组...
文中研究了一个类似欧拉函数φ(n)的新的Smarandache可乘数论函数J(n),其中J(n)为模n所有原Dirichlet特征的个数,即J(n)=n∏p|n(p-1)2.利用初等数论的方法解决了J(n)可乘数论函数在简单数序列中的均值问题,并给出了一...
欧拉函数是数论中很重要的一个函数,欧拉函数是指:对于一个正整数 n ,小于 n 且和 n 互质的正整数(包括 1)的个数,记作 φ(n) 。 完全余数集合: 定义小于 n 且和 n 互质的数构成的集合为 Zn ,称呼这个集合为...
50006 使用函数统计一个整数中数字的个数 45 50007 使用函数找水仙花数 46 50009 使用函数求余弦函数的近似值 48 50052 使用函数找最大值 49 50062 使用函数输出指定范围内的 Fibonacci 数 50 50063 使用函数找出...
定义 素数又称质数。...(6)若n为大于或等于2的正整数,在n到 之间至少有一个质数。 (7)若质数p为不超过n( )的最大质数,则 。 (8)所有大于10的质数中,个位数只有1,3,7,9 素数密度公式 根据
(1)参数n是一个整数,其取值范围为0~32767的整数。Spc函数与输出项之间用分号隔开。 (2)Spc函数和Tab函数作用类似,而且可以互相代替。二者有区别:Tab函数是从左端开始计数,而Spc函数只是表示两个输出项之间...
50006 使用函数统计一个整数中数字的个数 45 50007 使用函数找水仙花数 46 50009 使用函数求余弦函数的近似值 48 50052 使用函数找最大值 49 50062 使用函数输出指定范围内的 Fibonacci 数 50 50063 使用函数找出...
1.程序分析:判断素数的方法:用一个数分别去除2到sqrt(这个数),如果能被整除, 则表明此数不是素数,反之是素数。 【程序3】 题目:打印出所有的"水仙花数",所谓"水仙花数"是指一个三位数,其各位数字立方和...
100道题及答案 1.m个人的成绩存放在score数组中...3.请编写函数void fun(int x,int pp[],int *n),它的功能是:求出能整除x且不是偶数的各整数,并按从小到大的顺序放在pp所指的数组中,这些除数的个数通过形参n返回。
1. 编写一函数Prime(n),针对已知正整数n,判断该数是否为素数,如果是素数,返回True,否则返回False。 2. 斐波那契数列指的是这样一个数列:0、1、1、2、3、5、8、13、21、34、……,从第3项开始,每一项都等于前...