NEFU-1867 把酒问青天

NEFU-1867 把酒问青天

/ 0评 / 1444次 / 0

今天在OJ上遇到了一个有趣的问题

李白爱喝酒,更爱储存酒,于是他建了N个酒窖,第1个酒窖装1瓶酒,第2个酒窖装2瓶酒,。。。。。第N个酒窖装N瓶酒;一天唐高宗来看李白,给李白出了一个问题:把每个酒窖的酒的数量乘积,这个数叫做梅花酒数,这个数好大好大,但唐高宗想知道这个数有几位?

显然这个问题的需求是:给定正整数 N 求 N ! 的位数

在我刚拿到这个问题的时候我直觉认为这个题目所要考察的可能是我要将数字转换成多个字符串加以存储并运算。(因为按照N的范围就是unsigned long long都是不够的)这个过程需要借助sprintf函数来实现,所依赖的头函数是<stdio.h>

sprintf (char *str, const char *format, ...)

接下来为了实现乘法的运算我想到了劳动人民的传统智慧——竖式计算

譬如计算ABC×DEF时,我们其实是将其拆分开来运算的

ABC×DEF=C×F+10×B×F+100×A×F+C×10×E+10×B×10×E+100×A×10×E+C×100×D+10×B×100×D+100×A×100×D(看着有些绕人,其实在草稿纸上笔画两下也就明白了)。

这之后便是用双重for循环,再将各个乘积求和便可以实现大数的乘法。

但是另一个问题也接踵而至,也就是最后在合并数字的时候不可避免的会在一个庞大的由多个字符串所组成的系统里面进行数字的操作。光复杂不说还极有可能出现内存溢出的情况,远远超出了现时我的业务水平。

在之后实现数字拆分并存放到多个字符串的时候。我便彻底被这个过程的复杂度所劝退,在分块存储的时候需要使用到相关的结构体,代码量高度复杂,再一看提交的情况。!??

短暂停顿之后,我重新整理了一下思路回过来看问题。这时我才意识到,题目所要求的位数就是求位数,根本不需要也很难去求出这样一个巨大的数字。

记得有位名人曾经说过“一切的问题最后都可以归结到数学问题”。

曾经为了方便天文学研究而发明的对数正是专门适合于解决大量级问题的。同样,在这条题目里面,对数运算,是完美契合这条题目的数学工具

于是问题便迎刃而解,利用对数将放大的数字缩小到一个直观的量级当中,得到的也直接是需求的 位数 

/*
* @Author: Gehrychiang
* @Date: 2019-08-18 20:56:43
* @Last Modified by: Gehrychiang
* @Last Modified time: 2019-08-18 22:17:56
* @Email:gehrychiang@ailiyun.com
* @Website:www.yilantingfeng.site
*/
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    int num;
    cin >> num;
    double digit = 1;
    for (int i = 1; i <= num; ++i)
    {
        digit = digit + log10(i);
    }
    cout << (int)digit << endl;
    return 0;
}

小总结:一切问题本质上都是数学问题,我在看到这个题目时第一反应是想着用程序语言本身的奇技淫巧去解决却反而绕了远路。对于数学知识的灵活应用才是写好程序的关键所在。

发表回复

您的电子邮箱地址不会被公开。

你好 No.59613