tilblackout
tilblackout
采纳率87.5%
2018-11-29 14:31

C语言怎么用递归输出2的64次方

已采纳

这样肯定是不行的 输出不了64次方的

 int p(int n)
{
    if(n<2)
        return 1;
    if(n>=2)
        return 2*p(n-1)+1;
}

而且禁用了 函数返回double等类型
被禁用的关键字:循环语句for、while,甚至包括分支语句的switch、case、goto。
被禁用的头文件:match.h、stdlib.h。

被禁用的库函数:pow等。

刚刚把函数返回值变成float提示wrong answer 80%
如果写double 提示禁用了这个关键词。

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

1条回答

  • caozhy 从今以后生命中的每一秒都属于我爱的人 3年前
    #include "stdio.h"
    
    #include "string.h"
    
    #define MAX 500
    
    void i2ar(int i, int * r)
    {
        int j = 0;
        memset(r, 0, MAX * sizeof(int));
        while (i > 0)
        {
            r[j] = i % 10;
            j++;
            i /= 10;
        }
    }
    
    void arout(int * r)
    {
        int i = MAX - 1;
        while(1)
        {
            if (i == 0) break;
            if (r[i] != 0) break;
            i--;
        }
        for (int j = i; j >= 0; j--)
        {
            printf("%d", r[j]);     
        }
    }
    
    void mul(int *r, int * m1, int * m2)
    {
        int pre[MAX];
        memset(r, 0, MAX * sizeof(int));
        memset(pre, 0, MAX * sizeof(int));
        for (int i = 0; i < MAX; i++)
        {
            int carry = 0;
            for (int j = 0; j < MAX; j++)
            {
                int t = (pre[j] + r[j] + carry) % 10;
                carry = (pre[j] + r[j] + carry) / 10;
                r[j] = t;
            }
            memset(pre, 0, MAX * sizeof(int));
            carry = 0;
            for (int j = 0; j < MAX - i - 1; j++)
            {
                pre[j + i] = (m1[i] * m2[j] + carry) % 10;
                carry = (m1[i] * m2[j] + carry) / 10;
            }
        }
    }
    
    int main()
    {
        int N[MAX], N1[MAX], N2[MAX];
        i2ar(1, N);
        i2ar(2, N2);
        for (int i = 0; i < 64; i++)
        {
            mul(N1, N, N2);
            memcpy(N, N1, sizeof(int) * MAX);
        }
        arout(N);
    }
    

    18446744073709551616

    所有的循环,都可以修改为递归,为了简化起见,我只修改mul,输入输出等你采纳以后我再修改

    第一步,去掉外面的循环:

    void mul(int *r, int * m1, int * m2, int i = 0, int * pre = NULL)
    {
        int pre1[MAX];
        if (i == 0)
        {
            pre = pre1;
            memset(r, 0, MAX * sizeof(int));
            memset(pre, 0, MAX * sizeof(int));
        }
        if (i == MAX) return;
        int carry = 0;
        for (int j = 0; j < MAX; j++)
        {
            int t = (pre[j] + r[j] + carry) % 10;
            carry = (pre[j] + r[j] + carry) / 10;
            r[j] = t;
        }
        memset(pre, 0, MAX * sizeof(int));
        carry = 0;
        for (int j = 0; j < MAX - i - 1; j++)
        {
            pre[j + i] = (m1[i] * m2[j] + carry) % 10;
            carry = (m1[i] * m2[j] + carry) / 10;
        }
        mul(r, m1, m2, i + 1, pre);
    }
    

    第二步,去掉里面的循环

    void mul_loop1(int j, int carry, int *r, int * pre)
    {
        if (j == MAX) return;
        int t = (pre[j] + r[j] + carry) % 10;
        carry = (pre[j] + r[j] + carry) / 10;
        r[j] = t;
        mul_loop1(j + 1, carry, r, pre);
    }
    
    void mul_loop2(int i, int j, int carry, int * m1, int * m2, int * pre)
    {
        if (j == MAX - i - 1) return;
        pre[j + i] = (m1[i] * m2[j] + carry) % 10;
        carry = (m1[i] * m2[j] + carry) / 10;
        mul_loop2(i, j + 1, carry, m1, m2, pre);
    }
    
    void mul(int *r, int * m1, int * m2, int i = 0, int * pre = NULL)
    {
        int pre1[MAX];
        if (i == 0)
        {
            pre = pre1;
            memset(r, 0, MAX * sizeof(int));
            memset(pre, 0, MAX * sizeof(int));
        }
        if (i == MAX) return;
        mul_loop1(0, 0, r, pre);
        memset(pre, 0, MAX * sizeof(int));
        mul_loop2(i, 0, 0, m1, m2, pre);
        mul(r, m1, m2, i + 1, pre);
    }
    

    完整程序:

    // Q715182.cpp : Defines the entry point for the console application.
    //
    
    #include "stdafx.h"
    
    #include "stdio.h"
    
    #include "string.h"
    
    #define MAX 25
    
    void i2ar(int i, int * r)
    {
        int j = 0;
        memset(r, 0, MAX * sizeof(int));
        while (i > 0)
        {
            r[j] = i % 10;
            j++;
            i /= 10;
        }
    }
    
    void arout(int * r)
    {
        int i = MAX - 1;
        while(1)
        {
            if (i == 0) break;
            if (r[i] != 0) break;
            i--;
        }
        for (int j = i; j >= 0; j--)
        {
            printf("%d", r[j]);     
        }
    }
    
    void mul_loop1(int j, int carry, int *r, int * pre)
    {
        if (j == MAX) return;
        int t = (pre[j] + r[j] + carry) % 10;
        carry = (pre[j] + r[j] + carry) / 10;
        r[j] = t;
        mul_loop1(j + 1, carry, r, pre);
    }
    
    void mul_loop2(int i, int j, int carry, int * m1, int * m2, int * pre)
    {
        if (j == MAX - i - 1) return;
        pre[j + i] = (m1[i] * m2[j] + carry) % 10;
        carry = (m1[i] * m2[j] + carry) / 10;
        mul_loop2(i, j + 1, carry, m1, m2, pre);
    }
    
    void mul(int *r, int * m1, int * m2, int i = 0, int * pre = NULL)
    {
        int pre1[MAX];
        if (i == 0)
        {
            pre = pre1;
            memset(r, 0, MAX * sizeof(int));
            memset(pre, 0, MAX * sizeof(int));
        }
        if (i == MAX) return;
        mul_loop1(0, 0, r, pre);
        memset(pre, 0, MAX * sizeof(int));
        mul_loop2(i, 0, 0, m1, m2, pre);
        mul(r, m1, m2, i + 1, pre);
    }
    
    int main()
    {
        int N[MAX], N1[MAX], N2[MAX];
        i2ar(1, N);
        i2ar(2, N2);
        for (int i = 0; i < 64; i++)
        {
            mul(N1, N, N2);
            memcpy(N, N1, sizeof(int) * MAX);
        }
        arout(N);
    }
    
    
    

    如果问题解决,请点我回答左上角的采纳和向上箭头,采纳后,我将把i2ar和arout的循环也改写成递归。


    已经修改

    #include "stdio.h"
    
    #include "string.h"
    
    #define MAX 25
    
    void i2ar(int i, int * r, int initrun = 1, int j = 0)
    {
        if (initrun)
            memset(r, 0, MAX * sizeof(int));
        if (i <= 0) return;
        r[j] = i % 10;
        j++;
        i /= 10;
        i2ar(i, r, 0, j);
    }
    
    void arout_loop1(int * r, int * i)
    {
        if (*i == 0) return;
        if (r[*i] != 0) return;
        *i = *i - 1;
        arout_loop1(r, i);
    }
    
    void arout_loop2(int * r, int j)
    {
        if (j < 0) return;
        printf("%d", r[j]);
        arout_loop2(r, j - 1);
    }
    
    void arout(int * r)
    {
        int i = MAX - 1;
        arout_loop1(r, &i);
        arout_loop2(r, i);
    }
    
    void mul_loop1(int j, int carry, int *r, int * pre)
    {
        if (j == MAX) return;
        int t = (pre[j] + r[j] + carry) % 10;
        carry = (pre[j] + r[j] + carry) / 10;
        r[j] = t;
        mul_loop1(j + 1, carry, r, pre);
    }
    
    void mul_loop2(int i, int j, int carry, int * m1, int * m2, int * pre)
    {
        if (j == MAX - i - 1) return;
        pre[j + i] = (m1[i] * m2[j] + carry) % 10;
        carry = (m1[i] * m2[j] + carry) / 10;
        mul_loop2(i, j + 1, carry, m1, m2, pre);
    }
    
    void mul(int *r, int * m1, int * m2, int i = 0, int * pre = NULL)
    {
        int pre1[MAX];
        if (i == 0)
        {
            pre = pre1;
            memset(r, 0, MAX * sizeof(int));
            memset(pre, 0, MAX * sizeof(int));
        }
        if (i == MAX) return;
        mul_loop1(0, 0, r, pre);
        memset(pre, 0, MAX * sizeof(int));
        mul_loop2(i, 0, 0, m1, m2, pre);
        mul(r, m1, m2, i + 1, pre);
    }
    
    void main_loop(int *N, int *N1, int *N2, int i)
    {
        if (i >= 64) return;
        mul(N1, N, N2);
        memcpy(N, N1, sizeof(int) * MAX);
        main_loop(N, N1, N2, i + 1);
    }
    
    int main()
    {
        int N[MAX], N1[MAX], N2[MAX];
        i2ar(1, N);
        i2ar(2, N2);
        main_loop(N, N1, N2, 0);
        arout(N);
    }
    

    我几个函数的改写略有不同,比如对于一段代码,循环前后还有一些别的代码
    那么可以用一个变量来判断是第一次循环还是最后一次循环,然后分别执行头尾,别的执行循环体
    或者可以把中间的循环体提取出来作为一个函数。
    如果循环改变了某个变量,可以用指针,等等。
    总之,遇到这种类似的问题,思路就是一开始不要想递归,先用非递归把程序写出来,写正确,再改就好了。
    你让我直接写,我也写不出来。

    点赞 评论 复制链接分享