精华内容
下载资源
问答
  • C语言快速 快速取模

    千次阅读 2020-01-15 21:46:24
    C语言快速 快速取模 -求一个数的几方,一般的可以用到for循环,累乘 #include<stdio.h> int main() { int a,b,i,ans=1; scanf("%d%d",&a,&b); for(i=1; i<=b; i++) { ans=ans*a; } ...

    C语言快速幂 快速幂取模

    -求一个数的几次方,一般的可以用到for循环,累乘

    #include<stdio.h>
    int main()
    {
        int a,b,i,ans=1;
        scanf("%d%d",&a,&b);
        for(i=1; i<=b; i++)
        {
            ans=ans*a;
        }
        printf("%d\n",ans);
        return 0;
    }
    
    
    • 一般的还可以用到math函数pow
    #include<stdio.h>
    #include<math.h>
    int main()
    {
        int a,b,ans;
        scanf("%d%d",&a,&b);
        ans=pow(a,b);
        printf("%d\n",ans);
        return 0;
    }
    
    
    • 以上两种方法,时间复杂度为O(n),如果a和b过大,很容易就会溢出。
      这就运用到了快速幂的方法,大大缩短时间

    快速幂

    快速幂,就是快速的求解一个数的几次方
    例如 2^12,若用一般的方法,要累成12次,太浪费时间
    快速幂的方法呢,首先我们先将指数转化成二进制(十进制转二进制,可以用到短除法)
    12=123+122+021+020 即12=1100
    212=2(8+4)=28*24=2 ^ (23) *2 ^ (22)累乘要循环12次,快速幂只需要2次
    当二进制数上为1时进行幂运算,为0时不进行(即遇0只是将a累乘,遇1将值乘到最终结果)

    #include<stdio.h>
    int main()
    {
        int a,b,ans=1;
        scanf("%d%d",&a,&b);
        while(b!=0)
        {
            if(b&1)//相当于b%2!=0 即判断二进制此位置是否为1
                ans=ans*a;
            a=a*a;
            b>>=1;//整体向后移一位,即去掉最后一位
        }
        printf("%d",ans);
        return 0;
    }
    
    

    快速幂取模

    与快速幂差不多,在每次运算的时候要作mod m运算
    用到了一个公式 :
    (a * b) % c = ((a % c) * (b % c)) % c
    用快速幂取模的方法比直接求幂再取模的方法要快
    代码如下:

    #include<stdio.h>
    int main()
    {
        int a,b,c,ans=1;
        scanf("%d%d%d",&a,&b,&c);//a为底数,b为指数,c为取模的常数
        while(b!=0)
        {
            if(b&1)
                ans=(ans*a)%c;
            a=(a*a)%c;
            b>>=1;
        }
        printf("%d\n",ans);
        return 0;
    }
    
    
    展开全文
  • C语言 快速

    2018-11-25 23:24:20
    快速求a的b次幂。 &amp;lt;math.h&amp;gt;中的pow函数的时间复杂度为O(n),快速幂可以解决此问题。 求a^b如果将b进行处理,让其有某种规律进行运算。 在计算机中,按照二进的方式进行运算,所以将b=&...

    快速幂


    快速求a的b次幂。
    <math.h>中的pow函数的时间复杂度为O(n),快速幂可以解决此问题。

    求a^b如果将b进行处理,让其有某种规律进行运算。

    在计算机中,按照二进的方式进行运算,所以将b=>1011,ab=>a(23)*a(21)*a(2^0),所以将b二进为1的的乘上。

    #include<stdio.h>
    int main(){
        int a,b,arr=1;
        scanf("%d%d",&a,&b);
        while(b!=0){
            if((b&1)!=0)
                arr*=a;
            a*=a;
            b>>=1;
        }
        printf("%d",arr);
        return 0;
    }
    

    b&1:因为要寻找二进制为一的,&1就是“与”1,如果最后一位是1则a*b(开始2^0所以直接乘后边对b作用进行幂运算)


    a*=a:对b进行幂运算,如不考虑二进位是否为一,则是a2,a4,a8…=>a21,a22,a2^3…。


    b>>=1:将b二进向右移一位

    展开全文
  • C语言pow()函数:求x的y次方(次幂) 头文件: #include <math.h> pow() 函数用来求 x 的 y 次幂(次方),其原型为: double pow(double x, double y); pow()用来计算以x 为底的 y 次方值,然后将结果...
  • C语言的三种方法

    千次阅读 2021-02-05 16:30:22
    直接对x乘y int result(int x,int y) { int num=1; for (int i=1; i<=y; i++) { num*=x; } return num; } 这种方法有手就行,但是运行时间往往过长 二. 快速 主要利用递归,它的思想类似于分治,把大...

    用三种方法求幂值

    一. 暴力递归

    直接对x乘y次

    int result(int x,int y)
    {
        int num=1;
        for (int i=1; i<=y; i++) {
            num*=x;
        }
        return num;
    }
    

    这种方法有手就行,但是运行时间往往过长

    二. 快速幂

    主要利用递归,它的思想类似于分治,把大问题分割为小问题,再将小问题的结果合计为大问题的解
    t4=t2+t2 t^{4}=t^{2}+t^{2}
    所以我们可以对幂指数进行不断的二分,达到降低时间复杂度的效果

    int result(int x,int y)
    {
        if(y==0)return 1;
        if(y==1)return x;
        int t=result(x, y/2)*result(x, y/2);
        if(y%2==0)return t;
        else return t*x;
    }
    

    当幂指数y为奇数时,还要乘一次自身

    三 .二进制求幂

    假设指数为7,可写为
    7=22+21+20111 7=2^{2}+2^{1}+2^{0} 其二进制形式为111,且每一位都等于前一位的平方

    long long qpow(int base,int p){
        long long ans=1,tmp=base;//从底数开始乘,不停自乘
        while(p!=0){//指数不是0
            if(p&1){
                ans=(ans*tmp);
            }
            tmp=(tmp*tmp);//自乘
            p=p>>1;//访问下一位
        }
        return ans;
    }
    

    再此方法下,时间复杂度最低

    希望大家三连关注,嘻嘻,我会继续更新c语言和python方面的文章,希望大家多多支持。

    展开全文
  • 在知乎上看到一个问题,涉及到一个数的高次幂运算,想用自己初学者的水平,来写一写。 计算7的1919次方 因为int有限,装不开这个数,就用数组表示,每个int里面装一部分这个数,最后倒序输出数组。 这时候要注意的...

    在知乎上看到一个问题,涉及到一个数的高次幂运算,想用自己初学者的水平,来写一写。

    计算7的1919次方

    因为int有限,装不开这个数,就用数组表示,每个int里面装一部分这个数,最后倒序输出数组。
    这时候要注意的是数组中的进位问题,为了方便,我给出了函数"Frmt"作为辅助。

    #include <stdio.h>
    #include <stdlib.h>
    /*
     * Calculate the number : 7^199
     */
    #define TenMil 10000000
    #define MAXI 10000
    #define POW 1919
    int main()
    {
        FILE *fp;
        fp = fopen("./answer.txt", "w");
        int num[MAXI] = {
            0,
        };
        num[0] = 7;
        void Frmt(int *buffer);
        for (int i = 0; i < POW - 1; i++)
        {
            int j = 0;
            while (1)
            {
                if (num[j] == 0)
                    break;
                else
                {
                    num[j] *= 7;
                    j++;
                }
            }
            for (int ji = 0; ji < MAXI; ji++)
            {
                if (num[ji] == 0)
                    break;
                else
                {
                    Frmt(&num[ji]);
                }
            }
        }
        int i;
        for (i = MAXI - 1; i >= 0; i--)
        {
            if (num[i] != 0)
            {
                break;
            }
        }
        for (; i >= 0; i--)
        {
            fprintf(fp, "%d", num[i]);
        }
        fclose(fp);
        return 0;
    }
    void Frmt(int *buffer)
    {
        if (*buffer > TenMil)
        {
            *(buffer + 1) += *buffer / TenMil;
            *buffer = *buffer % TenMil;
        }
    }
    //system("pause");
    
    展开全文
  • 蓝桥杯练习场上有两个此类题目: 算法训练 方分解 时间限制:1.0s 内存限制:256.0MB ... 使用一个函数,递归的进行分解,每次分解的时候要将数字先...例如: 137=27+23+20 同时约定方用括号来表示,即a...
  • strassen算法-现实2次幂,偶数奇数 C语言实验
  • 运用递归实现k次幂运算,模拟手工计算 注释掉的输出部分便于调试过程中检查使用 使用说明:输入一个数字k,计算矩阵的k次幂,输出原矩阵以及其k次幂矩阵 矩阵的k次幂可用于以邻接矩阵存储的图的算法中,具体原理...
  • strassen算法-现实2次幂,偶数奇数 C语言实验
  • C语言 计算x的n次幂

    2021-03-26 23:04:33
    x=3,n=2 3的2次幂 scanf("%d%d",&x,&n);输入3 2后,下一步的int ret=outpow(x,n) 传递到函数体int outpow(int x, int n),因为n等于2,所以执行 x*outpow(x, n - 1) 开始递归,x*outpow(x, n - 1),把x=3,n=...
  • 将这种 2 进制表示写成 2 的次幂的和的形式,令次幂高的排在前面,可得到如下表 达式:137=27+23+2^0 现在约定幂次用括号来表示,即 a^b 表示为 a(b) 此时,137 可表示为:2(7)+2(3)+2(0) 进一步:7=22+2+20...
  • C语言开平方与求幂次

    2021-06-01 21:08:23
    c语言可以通过调用#include <math.h>头文件实现开平方与求幂次 a=sqrt(表达式); //开平方 a=pow
  • 试题 算法训练 2的次幂表示                              ...
  • 如果x的x次幂结果为10(参见【图1.png】),你能计算出x的近似值吗? 显然,这个值是介于2和3之间的一个数字。 请把x的值计算到小数后6位(四舍五入),并填写这个小数值。 注意:只填写一个小数,不要写任何多余...
  • C语言的求函数POW

    万次阅读 2012-10-23 10:05:40
    C语言中的数学函数:pow  原型:在TC2.0中原型为extern float pow(float x, float y);... 功能:计算x的y次幂。  返回值:x应大于零,返回幂指数的结果。  返回类型:double型,int,
  • 递归求x的n次幂C语言

    千次阅读 2020-05-11 09:46:17
    通过递归,减少累乘的次数。 1、n=0或x=1,直接返回1. 2、n>0,n为偶数,可将x^n拆分为 (x*x)^(n/2); 3、n>0,n为奇数,可将x^n拆分为x*(x*x)^((n-1)/2); 4、n<0,n为偶数,可将x^n拆分为1/((x*x)^(-n/2);...
  • C语言使用递归计算m的n次幂

    千次阅读 2019-02-21 16:16:19
    #include <stdio.h> int mton(int m, int n) { if (n == 1) return m; else { return m * mton(m, n - 1); } } int main() { printf("%d\n", mton(2, 3)); //system("pause"...
  • 将这种2进制表示写成2的次幂的和的形式,令次幂高的排在前面,可得到如下表达式:137=2^7+2^3+2^0 现在约定幂次用括号来表示,即a^b表示为a(b) 此时,137可表示为:2(7)+2(3)+2(0) 进一步:7=2^2+2+2^0 (2^...
  • 问题要求: 设计一个递归函数,求x的n次幂;主函数通过键盘输入x和n的值,并输出x^n的值。(假设x为实数,n为正整数) Code: #include<stdio.h> // 计算x^n的函数 float fun(float x, int n){ if(n==0) ...
  • Q1:判断一个数是否是2的整数次幂 A1:从二进制的角度思考,就很容易得出答案 int func(int num) { return((num > 0) && (num & (num - 1)) == 0); } Q2:利用异或交换两数的值 A1: #...
  • #include &lt;stdio.h&gt; #define is_power_2(x) ((x&gt;0) &amp;&amp; (0 == (x&amp;(x-1)))) int main() { for(int i=0; i&lt;63; i++) { printf("... 
  • 一万以内2的整数次幂问题描述语法思路代码其他 问题描述 输出1~10000以内2的整数次幂。 语法 do while 循环语句特点:至少执行一次。 do{     循环主体 } while (条件); 流程图(每次): ...
  • 自幂数是指一个 n 位数,它每位上的数字的 n 次幂之和等于它本身。 (例如:153,n=3,13+53+33=153 ,153即是n为3时的一个自幂数) 1.2自幂数别名 一位自幂数:独身数 两位自幂数:没有 三位自幂数:水仙花数 ...
  •  将这种2进制表示写成2的次幂的和的形式,令次幂高的排在前面,可得到如下表达式:137=27+23+2^0  现在约定幂次用括号来表示,即a^b表示为a(b)  此时,137可表示为:2(7)+2(3)+2(0)  进一步:7=22+2+20 ...
  • 如果x的x次幂结果为10,你能计算出x的近似值吗?显然,这个值是介于2和3之间的一个数字。请把x的值计算到小数后6位(四舍五入),并填写这个小数值。需要用到的函数fabs(double x),求x的绝对值;pow(x,y),求x^y的值...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 591
精华内容 236
关键字:

c语言次幂

c语言 订阅