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 提示禁用了这个关键词。

caozhy
贵阳老马马善福专业维修游泳池堵漏防水工程 我更新了答案,你可以看下,有问题请追问。
一年多之前 回复

1个回答

#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);
}

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

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐