花露水和暖壶


私信TA

用户名:MichaelMeng

访问量:8457

签 名:

等  级
排  名 81
经  验 9130
参赛次数 0
文章发表 28
年  龄 0
在职情况 学生
学  校 烟台大学
专  业

  自我简介:

不喜欢摇滚乐的研究生不是好程序猿!

TA的其他文章

解题思路:其实此题考察了两个知识点,一是汉诺塔的问题,二是对大数的处理,汉诺塔的问题网上的解析都已经烂大街了,n个圆盘移动的次数(2^n-1),本题是2n个盘子,那就是2*(2^n-1),3n个盘子结果就是3*(2^n-1)...依此类推,计算不是问题,当你套进公式,兴冲冲去提交,不出所料,答案错误。
公式没错,问题是此题中当n很大时,结果直接指数爆炸,经过测试,当n取150时,使用long long直接溢出,我tm直接好家伙,long long都满足不了它,年轻人不讲武德,这好吗,这不好!


    那么如何解决大数的表示呢——使用数组模拟大数。我简单讲下原理:例如定义int bigNumber[100],数组中的每一位都表示这个超级大数的一位数字,如果一个数字是12345678925364758698362514, 把它映射到数组中就是bigNumber[0] = 1、bigNumber[1] = 2、bigNumber[2] = 3......依此类推,如果100位还不满足,你可以定义数组长度位1000、100000都行,绝对能解决大数问题。
    那么代码该怎么写出来,本题解参照了大佬的博客(博客地址), 感兴趣的可以去膜拜一下,废话不多说,直接上代码,搭配上注释,应该没问题,如果还不懂,Q1782356223找我:

//说明代码的功能,计算2*(2^n-1)的值。

#include <stdio.h>

int main() {
    int n = 0;//圆盘的个数,说到底就是你想算2的多少次幂
    scanf("%d", &n);
    int bigNumber[n];//用于存储超级大数,当然这里的n你可以写成100、1000、10000都行

    //先把数组初始化元素全部设为0
    for (int i = 0; i < n; ++i) {
        bigNumber[i] = 0;
    }

    //开始计算2^n,注意这里仅仅是计算2^n、2^n、2^n,还没到减1的那一步
    //注意,这里是将数组“颠倒”使用的,bigNumber[0]表示大数的最后一位(个位数字),bigNumber[n]表示大数的最高位,至于原因,看下去就知道了
    
    
    bigNumber[0] = 1;//第一位等于1,以便进行乘积运算,要不然0^n结果全部都是0
    for (int i = 0; i < n; ++i) {//这里的n表示乘积次数,你想求2的多少次幂,这里就写几
        for (int j = 0; j < n; ++j) {
            bigNumber[j] *= 2;//每次遍历,数组中的每一位都要乘2。例如计算123*2时,1、2、3都要乘2,这里原理一样
        }
        
        //乘法做完了,现在开始挨个位检查,看看哪位数值超过了9
        for (int k = 0; k < n; ++k) {
            if (bigNumber[k] > 9) {
                bigNumber[k+1]++;//如果某一位数超过了9,则需要进位
                bigNumber[k] = bigNumber[k]%10;//进位后自身取余,例如13%10=3
            }
        }
    }

    
    
    //现在开始执行2^n-1操作
    bigNumber[0]-= 1;//放心减1,因为2^n个位数绝对只能是2、4、8、6...

    
    
    //现在开始执行2*(2^n-1),说白了也就是将大数整体再乘一次2,原理同上方的次幂完全相同,只不过部分位置的循环条件发生变化
    
    for (int i = 0; i < 1; ++i) { //这里的i从n变为1,就变了这一个地方,因为只进行一次乘2操作,其余的啥都没变
        
        for (int j = 0; j < n; ++j) {
            bigNumber[j] *= 2;//每次遍历,数组中的每一位都要乘2,例如123*2时1、2、3都要乘2
        }
        
        //乘法做完了,现在开始挨个位检查,看看哪位数值超过了9
        for (int k = 0; k < n; ++k) {
            if (bigNumber[k] > 9) {
                bigNumber[k+1]++;//如果某一位数超过了9,则需要进位
                bigNumber[k] = bigNumber[k]%10;//进位后自身取余, 例如13%10=3
            }
        }
    }


    //好了,结果已经计算完毕,现在就是输出结果
    for (int i = n-1; i >= 0 ; --i) {
        //数组中可能出现一些位为0,没用上,那就把这些0找出来,例如123450000000000,后面的那一堆0要他何用?不输出它
        if (bigNumber[i] > 0) {
        
            //找到了第一个不为0的位,也就是大数的“最高位”,注意,这里是将数组“颠倒”使用的,bigNumber[0]表示大数的最后一位(个位数字),
            //bigNumber[n]表示大数的最高位,至于原因,看下去就知道了
            for (int j = i; j >= 0; --j) {  //"倒“着输出数组的每一位即可
                printf("%d", bigNumber[j]);
            }
            break;
        }
    }
    return 0;
}

完结撒花,我写到这里的时候,又把代码复制重新提交了一遍,依旧通过,小伙伴可放心使用!


 

0.0分

15 人评分

  评论区

这个数组表示大数,对经历了两次longlong都溢出的我来讲,很难不爱!!
2022-08-29 17:30:38
哈哈哈好暴力好喜欢
2021-12-05 22:57:52
  • «
  • 1
  • »