最少乘法次数,面试算法知识梳理4887王中王鉄算

来源:http://www.smjxgs.com 作者:王中王鉄算盘 人气:125 发布时间:2019-08-29
摘要:NYOJ 46-最少乘法次数(数论)   思路:可以化成二进制来求解,结果是最高位的位数-1 最高位后面1的个数。例如:对于3,它的二进制代码为11,就是用这个最高位(2-1)加上后面的1的个数

NYOJ 46-最少乘法次数(数论)

 

思路:可以化成二进制来求解,结果是最高位的位数-1 最高位后面1的个数。例如:对于3,它的二进制代码为11,就是用这个最高位(2-1)加上后面的1的个数(1个)。

用最高位1的目的是他能代表了转化的次数,因为2 2=4,4 4=8 8 8=16........

 

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
using namespace std;
typedef long long LL;
const int inf=0x3f3f3f3f;
const double pi= acos(-1.0);
const double esp=1e-6;
const int maxn=21010;
char str[110];
int main()
{
    int T,n,i,j;
    int cnt;
    scanf(%d,&T);
    while(T--){
        scanf(%d,&n);
        memset(str,0,sizeof(str));
        i=0;
        while(n/2!=0){
            str[i  ]='0' n%2;
            n=n/2;
        }
        str[i]='1';
        cnt=0;
        for(j=0;j  

46-最少乘法次数(数论) 思路:可以化成二进制来求解,结果是最高位的位数-1 最高位后面1的个数。例如:对于3,它的二进制代码为11,...

面试算法代码知识梳理系列

面试算法知识梳理(1) - 排序算法
面试算法知识梳理(2) - 字符串算法第一部分
面试算法知识梳理(3) - 字符串算法第二部分
面试算法知识梳理(4) - 数组第一部分
面试算法知识梳理(5) - 数组第二部分
面试算法知识梳理(6) - 数组第三部分
面试算法知识梳理(7) - 数组第四部分
面试算法知识梳理(8) - 二分查找算法及其变型
面试算法知识梳理(9) - 链表算法第一部分
面试算法知识梳理(10) - 二叉查找树
面试算法知识梳理(11) - 二叉树算法第一部分
面试算法知识梳理(12) - 二叉树算法第二部分
面试算法知识梳理(13) - 二叉树算法第三部分


题目描述:

亲们!!我们的外国友人YZ这几天总是睡不好,初中奥数里有一个题目一直困扰着他,特此他向JOBDU发来求助信,希望亲们能帮帮他。问题是:求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数?为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数。

 

输入:
输入有多组数据,每组测试数据为一行。

每一行有两个整数a,b(0<=a,b<=1,000,000,000)。

 

输出:
对应每个测试案例,输出a和b之间1出现的次数。

 

样例输入:

0 5
1 13
21 55
31 99

 

样例输出:

1
6
4
7

一、目录

  • 斐波那契数列(循环算法、矩阵算法)
  • 跳台阶问题
  • 数值的整数次方
  • 打印1到最大的n位数
  • 计算从1n1出现的个数
  • 求两个数的二进制表示中有多少个是不同的
  • 给定一个整数N,求N!的末尾有多少个0
  • 给定一个整数N,求N!的二进制表示中最低位1的位置
  • 最大公约数
  • 精确地表达有限/无限循环小数

解题思路:

  这道题目要注意几个问题:

  第一个,比如10 到15 出现几个1?是7个...数字10 12 13 14 15各出现一次,11出现两次,因此是7次

  第二个,输入的两个数,第一个数,可能比第二个大。因此如果第一个数大于第二个数要进行一次调整。

    if(n>m)
            swap(&n,&m);

 

  第三个,就是这道题的主要思想。

  主要思想,通过递归来求解。我们分别求出两个数含有1的个数,但是要注意,对小的的数求解时,要减1.因为如果是10到15,0到10应该含有2个1,而0到15含有8个1,如果直接相减,10的那个1就被减掉了。因此要减1求解。

     char numN[MAXSIZE];
        char numM[MAXSIZE];
        sprintf(numN,"%d",n-1);
        sprintf(numM,"%d",m);
        numberOfN = getNumber(numN);
        numberOfM = getNumber(numM);
        printf("%dn",numberOfM-numberOfN);

 

  算法主要思想,首先我们看最高位。把数分解,abcde就分解成bcde 1到abcde 与 1到bcde两段。比如,34567分解成4568到34567,1到4567.这样求解第一段,只需要考虑第一位,和后面几位的普通情况就行了。然后递归求第二段。

  如果最高位是大于1的数。那么就分包含1的情况,和1以外的情况。

  对于最高位是1的,后面无论是什么都满足情况。因此,如果高位刚好等于1,那么满足的情况更应该是后面的数字之和。举个例子,

  12345,最高位为1时,满足的情况为2345种(不考虑后面的)。

    numF = 0;
    if(firstNum > 1)
        numF = power(length-1);
    else if(firstNum == 1)
        numF = atoi(num 1) 1;        

 

  而22345,最高位大于1时,满足的情况为10000-19999,即10000种。

  接下来,分析下最高位不是1时候,应该就是后面的个个位数为1其他位随机的数目。即,first*(lengt-1)*power(length-2),即在本例中为2*4*1000种,即11000,11001,11002,11003...21000,21002,21003,21004...即每一位为1*其他几位的随机数。此处就是4*1000.

int getNumber(const char *num){
    int firstNum = *num-'0';
    int length = strlen(num);
    int numF,numOther,numL;
    if(!num || *num < '0' || *num > '9' || *num == '\0')
        return 0;
    if(length == 1 && firstNum == 0)
        return 0;
    if(length == 1 && firstNum > 0)
        return 1;

    numF = 0;
    if(firstNum > 1)
        numF = power(length-1);
    else if(firstNum == 1)
        numF = atoi(num 1) 1;

    numOther = firstNum*(length-1)*power(length-2);

    numL = getNumber(num 1);

    return numF   numOther   numL;
}

二、代码实现

全部代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 32
int getNumber(const char *num);
int power(int length);
void swap(int *a,int *b);
int main(){
    int n,m,numberOfN,numberOfM;
    while(scanf("%d %d",&n,&m)!=EOF ){
        if(n>m)
            swap(&n,&m);
        char numN[MAXSIZE];
        char numM[MAXSIZE];
        sprintf(numN,"%d",n-1);
        sprintf(numM,"%d",m);
        numberOfN = getNumber(numN);
        numberOfM = getNumber(numM);
        printf("%dn",numberOfM-numberOfN);
        //printf("%dn",n == 1?(numberOfM - numberOfN 1):(numberOfM-numberOfN));
    }
    return 0;
}
int getNumber(const char *num){
    int firstNum = *num-'0';
    int length = strlen(num);
    int numF,numOther,numL;
    if(!num || *num < '0' || *num > '9' || *num == '\0')
        return 0;
    if(length == 1 && firstNum == 0)
        return 0;
    if(length == 1 && firstNum > 0)
        return 1;

    numF = 0;
    if(firstNum > 1)
        numF = power(length-1);
    else if(firstNum == 1)
        numF = atoi(num 1) 1;

    numOther = firstNum*(length-1)*power(length-2);

    numL = getNumber(num 1);

    return numF   numOther   numL;
}
int power(int length){
    int i;
    int result = 1;
    for(i=0;i<length;i  ){
        result *= 10;
    }
    return result;
}
void swap(int *a,int *b){
    int tmp = *b;
    *b = *a;
    *a = tmp;
}
/**************************************************************
    Problem: 1373
    User: xhalo
    Language: C
    Result: Accepted
    Time:10 ms
    Memory:916 kb
****************************************************************/

 

2.1 斐波那契数列(循环算法、矩阵算法)

问题描述

斐波那契数列 满足下面的通项公式,要求给出N,输出第N项的F(N)

F(0)=0, F(1)=1, F(n)=F(n-1) F(n-2)(n>=2,n∈N*)

解决思路

这里介绍两种解决办法,循环算法矩阵算法。循环算法比较容易理解,就是从F(0)开始,根据通项公式,得到下一个斐波那契数列中的数字即可。

循环算法代码实现

class Untitled {

    static double fibonacci(int n) {
        if (n < 2) {
            return n;
        }
        //f(n-2)
        double fnMinus2 = 0;
        //f(n-1)
        double fnMinus1 = 1;
        double result = 0;
        for (int i=2; i<=n; i  ) {
            //根据通项公式计算。
            result = fnMinus2   fnMinus1;
            fnMinus2 = fnMinus1;
            fnMinus1 = result;
        }
        return result;
    }

    public static void main(String[] args) {
        double loopResult = fibonacci(10);
        System.out.println("loopResult="   loopResult);
    }
}

循环算法运行结果

>> loopResult=55.0

矩阵算法解决思路

对于上面的通项公式,可以用下面的矩阵乘法的形式来表示

4887王中王鉄算盘奖结果 1

那么,我们的问题就变成了求该特殊矩阵的N-1次方的值。

矩阵算法代码实现

class Untitled {

    static class Matrix {

        double a;
        double b;
        double c;
        double d;

        public Matrix(double a, double b, double c, double d) {
            this.a = a;
            this.b = b;
            this.c = c;
            this.d = d;
        }
    }

    //矩阵乘法函数。
    static Matrix multiMatrix(Matrix a, Matrix b) {
        Matrix result = new Matrix(0, 0, 0, 0);
        result.a = a.a*b.a   a.b*b.c;
        result.b = a.a*b.b   a.b*b.d;
        result.c = a.c*b.a   a.d*b.c;
        result.d = a.c*b.b   a.d*b.d;
        return result;
    }

    //核心函数。
    static double fibonacciMatrix(int n) {
        if (n < 2) {
            return n;
        }
        Matrix r = new Matrix(1, 0, 0, 1);
        Matrix tmp = new Matrix(1, 1, 1, 0);
        n--;
        while (n > 0) {
            if ((n&1) > 0) {
                r = multiMatrix(r, tmp);
            }
            tmp = multiMatrix(tmp, tmp);
            n >>= 1;
        }
        return r.a;
    }

    public static void main(String[] args) {
        double matrixResult = fibonacciMatrix(10);
        System.out.println("matrixResult="   matrixResult);
    }
}

矩阵算法运行结果

>> matrixResult=55.0

2.2 跳台阶问题

问题描述

一个台阶总共有n级,如果一次可以跳1级,也可以跳2级,求总共有多少总跳法。

解决思路

由于有两种跳台阶方式,因此跳n级台阶可以转换为下面两个问题之和:

  • 第一次跳1级台阶,之后的解法数为f(n-1)
  • 第一次跳2级台阶,之后的解法数为f(n-2)

这就和之前的斐波那契数列的通项公式相同。

实现代码

class Untitled {

    static class Matrix {

        double a;
        double b;
        double c;
        double d;

        public Matrix(double a, double b, double c, double d) {
            this.a = a;
            this.b = b;
            this.c = c;
            this.d = d;
        }
    }

    //矩阵乘法函数。
    static Matrix multiMatrix(Matrix a, Matrix b) {
        Matrix result = new Matrix(0, 0, 0, 0);
        result.a = a.a*b.a   a.b*b.c;
        result.b = a.a*b.b   a.b*b.d;
        result.c = a.c*b.a   a.d*b.c;
        result.d = a.c*b.b   a.d*b.d;
        return result;
    }

    //核心函数。
    static double fibonacciMatrix(int n) {
        if (n < 2) {
            return n;
        }
        Matrix r = new Matrix(1, 0, 0, 1);
        Matrix tmp = new Matrix(1, 1, 1, 0);
        n--;
        while (n > 0) {
            if ((n&1) > 0) {
                r = multiMatrix(r, tmp);
            }
            tmp = multiMatrix(tmp, tmp);
            n >>= 1;
        }
        return r.a;
    }

    static double stepCounter(int step) {
        if (step <= 2) {
            return step;
        }
        return fibonacciMatrix(step);
    }


    public static void main(String[] args) {
        double count = stepCounter(50);
        System.out.println("counter="   count);
    }
}

2.3 数值整数次方

实现代码

class Untitled {

    static double powerOfNum(int num, int power) {
        int tmp = num;
        int r = 1;
        while (power > 0) {
            //如果在该位上为1,那么就乘上对应的n次方。
            if ((power&1) > 0) {
                r = r*tmp;
            }
            tmp = tmp*tmp;
            power >>= 1;
        }
        return r;
    }


    public static void main(String[] args) {
        System.out.println("powerOfNum="   powerOfNum(2, 10));
    }
}

运行结果

>> powerOfNum=1024.0

2.4 打印 1 到最大的 n 位数

class Untitled {

    static void printNumberCore(int p[], int depth, int len) {
        //到达末尾,打印当前数组中的元素。
        if (depth == len 1) {
            StringBuilder builder = new StringBuilder();
            for (int i=1; i<=len; i  ) {
                builder.append(String.valueOf(p[i]));
            }
            System.out.println(builder.toString());
            return;
        }
        //如果是首位,那么从1开始,否则从0开始。
        int pStart = 0;
        if (depth == 1) {
            pStart = 1;
        }
        for (int i=pStart; i<=9; i  ) {
            //替换该位,并进行递归。
            p[depth] = i;
            printNumberCore(p, depth 1, len);
        }
    }

    static void printNumber(int n) {
        //首先建立数组。
        int p[] = new int[n 1];
        //len表示有几位数。
        for (int len=1; len<=n; len  ) {
            //对应于len位数的全排列。
            printNumberCore(p, 1, len);
        }
    }

    public static void main(String[] args) {
        printNumber(3);
    }
}

2.5 计算从 1 到 n 中 1 出现的个数

解决思路

这个问题,需要先总结一下规律,我们根据数字N位数 来进行分析:

一位数

那么N>=1时才会出现1,并且出现1的次数为1

两位数

在这种情况下,出现1的次数等于个位上出现1的次数加上十位上出现1的个数。

  • 个位上出现1的次数不仅和个位的数字有关,还和十位的数字有关:

    • 如果个位为0,那么个位上出现1的次数等于十位的数字。
    • 如果个位大于0,那么个位上出现1的次数等于十位的数字加1
  • 十位上出现1的次数不仅和十位的数字有关,还和个位的数字有关:

    • 如果十位为1,那么十位上出现1的次数等于个位的数字加1
    • 如果十位大于1,那么十位上出现1的次数等于10

N 位数

例如,如果要计算百位上1出现的次数,它要受到三方面的影响:百位上的数字,百位以下的数字,百位以上的数字。

  • 如果百位上数字为0,百位上可能出现1的次数仅由更高位决定,等于更高位数字乘以当前位数。

  • 如果百位上数字为1,百位上可能出现1的次数不仅受更高位影响还受低位影响:

    • 受高位影响的部分等于更高位数字乘以当前位数
    • 受低位影响等于低位数字加上1
  • 如果百位上数字大于1,则百位上出现1的情况仅由更高位决定,等于更高位数字加上1乘以当前位数。

代码实现

class Untitled {

    static int countOneNum(int data) {
        int iFac = 1;
        int countNum = 0;
        int lowNum = 0;
        int curNum = data % 10;
        int highNum = data / 10;
        //从个位数开始遍历,每次while循环向前移动一位,计算每一位出现1的次数,总和就是问题的解。
        while (curNum > 0 || highNum > 0) {
            if (curNum == 0) {
                countNum  = highNum * iFac;
            } else if   (curNum == 1) {
                countNum  = highNum * iFac   (lowNum   1);
            } else {
                countNum  = (highNum 1)*iFac;

            }
            lowNum = lowNum   curNum*iFac;
            curNum = highNum % 10;
            highNum = highNum / 10;
            iFac *= 10;
        }
        return countNum;
    }


    public static void main(String[] args) {
        System.out.println("n="   123   ",result="   countOneNum(123));
    }
}

运行结果

>> n=123,result=57

2.6 求两个数的二进制表示中有多少个是不同的

解决思路

对于一个二进制数,例如1010,将其减1后得到的结果是1001,也就是将最后一个1(倒数第二位)及其之后的0变成11变成0,再将该结果与原二进制数相与,也就是1010 & 1001 = 1000,那么就可以去掉最后一个1

因此,如果需要计算两个数的二进制表示中有多少位是不同的,可以 先将这两个数异或,那么不相同的位数就会变成1,之后利用上面的技巧,通过每次去掉最后一个1,来 统计该结果中1的个数,就可以知道两个数的二进制表示中有多少是不同的了。

代码实现

class Untitled {

    static int getDiffBit(int a, int b) {
        int diff = a^b;
        int count = 0;
        while (diff > 0) {
            count  ;
            diff = diff & (diff-1);
        }
        return count;
    }


    public static void main(String[] args) {
        System.out.println("result="   getDiffBit(1999, 2299));
    }
}

运行结果

>> result=7

2.7 给定一个整数 N,求 N! 的末尾有多少个 0

问题描述

N!的含义为1*2*3*...*(N-1)*N,计算N!的十进制表示中,末尾有多少个0

解答思路

N!中能产生末尾是0的质数组合是2*5,所以N!末尾的0的个数取决了2的个数和5的个数的最小值,有因为被2整除的数出现的概率大于5,因此5出现的次数就是N!末尾0的个数。因此,该问题就转换成为计算从1~N,每个数可以贡献5的个数,也就是每个数除以5的值。

上面的解法需要从1N遍历每一个数,当然还有更加简便的方法。以26!为例,贡献5的数有5、10、15、20、25,一共贡献了65,可以理解为5的倍数5、10、15、20、25贡献了一个5,而25的倍数又贡献了一个5,得到下面的公式:

Z = [N/5]  [N/5^2]  [N/5^3]   …(总存在一个K,使得5^K > N,[N/5^K]=0)

代码实现

class Untitled {

    static int lowZeroN(int N) {
        int count = 0;
        while (N > 0) {
            N = N / 5;
            count = count   N;
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println("26!的十进制表示中末尾0的个数="   lowZeroN(26));
    }
}

运行结果

>> 26!的十进制表示中末尾0的个数=6

2.8 给定一个整数 N,求 N! 的二进制表示中最低位 1 的位置

解答思路

首先,让我们换一个角度考虑,其实这个问题就是求解二进制表示中从最低位开始0的个数,因为二进制最低位为0代表的是偶数,能够被2整除,所以质因数2的个数就是二进制表示中最低位1后面的0的个数。

因此,我们的实现这就和上面2.7中求解质因数5的个数是一样的。

代码实现

class Untitled {

    static int lowOneN(int N) {
        int count = 0;
        while (N > 0) {
            N = N >> 1;
            count = count   N;
        }
        return count 1;
    }

    public static void main(String[] args) {
        System.out.println("3!的二进制表示中最低位1的位置="   lowOneN(3));
    }
}

运行结果

>> 3!的二进制表示中最低位1的位置=2

2.9 最大公约数

问题描述

最大公约数 的定义为 两个或多个整数的共有约数中最大的一个。这里采用的是 更相止损法,其操作步骤为:

  • 第一步:任意给定两个正整数;判断它们是否都是偶数。若是,则用2约简;若不是则执行第二步。
  • 第二步:以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的减数和差相等为止。

则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。

代码实现

class Untitled {

    static int gcd(int big, int small) {
        int fac = 1;
        int temp;
        while (small > 0) {
            //保证数字的先后顺序。
            if (small > big) {
                temp = big;
                big = small;
                small = temp;
            }
            if ((big & 1) > 0) {
                //奇奇。
                if ((small & 1) > 0) {
                    temp = big;
                    big = small;
                    small = temp - small;
                //奇偶。
                } else {
                    small >>= 1;
                }
            } else {
                //偶奇。
                if ((small & 1) > 0) {
                    big >>= 1;
                //偶偶。
                } else {
                    small >>= 1;
                    big >>= 1;
                    fac *= 2;
                }
            }
        }
        return big * fac;
    }


    public static void main(String[] args) {
        int result = gcd(319, 377);
        System.out.println("result="   result);
    }
}

运行结果

>> result=29

2.10 精确地表达有限/无限循环小数

问题描述

有限小数或者无限循环小数都可以转化为分数,例如:

有限小数:0.9 = 9/10
无限循环小数:0.333(3)= 1/3

解决思路

在 http://blog.csdn.net/flyfish1986/article/details/47783545 这边文章中,详细地描述了该题的解决思路,核心思想就是将原小数分为 有限部分无限循环小数 部分,对于这两部分别进行处理。

4887王中王鉄算盘奖结果 2

算法核心思想

代码实现

class Untitled {

    public static class Fraction {
        //分子。
        public double numerator;
        //分母。
        public double denominator;
    }

    public static double powerOf(int num, int mi) {
        double temp = 10;
        double result = 1;
        while (mi > 0) {
            if ((mi & 1) > 0) {
                result = result * temp;
            }
            temp = temp * temp;
            mi >>= 1;
        }
        return result;
    }

    //分为有限循环和无限循环两个部分,按照公式计算。
    public static Fraction getDescription(int limit, int limitLen, int unLimit, int unLimitLen) {
        //分别计算对应长度的10的n/m次幂。
        double limitPower = powerOf(10, limitLen);
        double unLimitPower = powerOf(10, unLimitLen);
        Fraction fraction = new Fraction();
        //根据公式计算分子和分母即可。
        fraction.numerator = limit * (unLimitPower - 1)   unLimit;
        fraction.denominator = (unLimitPower - 1) * limitPower;
        return fraction;
    }

    public static void main(String[] args) {
        Fraction f = getDescription(285714, 6, 285714, 6);
        System.out.println("res= "   f.numerator   "/"   f.denominator);
    }
}

运行结果

>> res= 2.85714E11/9.99999E11

更多文章,欢迎访问我的 Android 知识梳理系列:

  • Android 知识梳理目录:http://www.jianshu.com/p/fd82d18994ce
  • Android 面试文档分享:http://www.jianshu.com/p/8456fe6b27c4

本文由4887王中王鉄算盘奖结果发布于王中王鉄算盘,转载请注明出处:最少乘法次数,面试算法知识梳理4887王中王鉄算

关键词:

上一篇:C的对象模型和runtime机制

下一篇:没有了

最火资讯