如何优雅地利用C++编程从1乘到20

墨蓝 2023-10-06 11:44 4阅读 0赞

数学家版本：

#include <iostream>
    #include <cmath>
    int main()
    {
        
        std::cout << std::tgamma(20 + 1) << std::endl;
    }

语言学家版本：

#include <iostream>
    #include <utility>
    
    template<std::size_t...I> constexpr auto foo(std::index_sequence<I...>) {
         return ((I+1) * ...); }
    
    int main() 
    {
        
        std::cout << foo(std::make_index_sequence<20>()) << std::endl;
    }

“快速”版本：

#include <iostream>
    #include <future>
    
    long long foo(int a, int b, std::future<long long> last = std::async(std::integral_constant<long long, 1>())) {
        
        return a == b ? a * last.get() : foo((a + b) / 2 + 1, b, std::async(foo, a, (a + b) / 2, std::move(last)));
    }
    
    int main() {
        
        std::cout << foo(1, 20) << std::endl;
    }

历史学家版本：

#include <stdio.h>
    void main(void) {
        
        int i;
        long long j;
        for(i = 1, j = 1;i <= 20; j *= i++);
            printf("%lld", j); }

敏捷开发上线1.0版本：

#include <stdio.h>
    int main() {
        
        //printf("%d", 1*2*3*4*5*6*7*8*9*10);
        printf("%lld", (long long)1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19*20);
    }

面向对象专家版本：

#include <iostream>
    #include <string>
    #include <memory>
    
    struct IBaseInterface {
        
        virtual ~IBaseInterface() = 0;
    };
    inline IBaseInterface::~IBaseInterface() = default;
    
    struct IDataProvider : virtual public IBaseInterface {
        
        virtual int first() = 0;
        virtual int last() = 0;
        virtual int next(int v) = 0;
    };
    
    struct ICalculator : virtual public IBaseInterface {
        
        virtual long long calc(IDataProvider *) = 0;
    };
    
    struct IPrinter : virtual public IBaseInterface {
        
        virtual void print(const std::string &) = 0;
    };
    
    struct ISerializer : virtual public IBaseInterface {
        
        virtual std::string serialize(long long value) = 0;
    };
    
    struct IRunnable : virtual public IBaseInterface {
        
        virtual void run() = 0;
    };
    
    class Foo : virtual public IRunnable {
        
        std::shared_ptr<IDataProvider> m_dp;
        std::shared_ptr<ICalculator> m_c;
        std::shared_ptr<ISerializer> m_s;
        std::shared_ptr<IPrinter> m_p;
    public:
        Foo(std::shared_ptr<IDataProvider> dp, std::shared_ptr<ICalculator> c, std::shared_ptr<ISerializer> s, std::shared_ptr<IPrinter> p) : m_dp(std::move(dp)), m_c(std::move(c)), m_s(std::move(s)),m_p(std::move(p)) {
        }
        void run() override {
         return  m_p->print(m_s->serialize(m_c->calc(m_dp.get()))); }
    };
    
    class DefaultSerializer : virtual public ISerializer {
        
    public:
        std::string serialize(long long value) override {
         return std::to_string(value); }
    };
    
    class StreamPrinter : virtual public IPrinter {
        
        std::ostream &m_os;
    public:
        explicit StreamPrinter (std::ostream &os) : m_os(os) {
        }
        void print(const std::string &s)  override {
         m_os << s << std::endl; }
    };
    
    class MultiplyAccumulateCalculator : virtual public ICalculator {
        
    public:
        long long calc(IDataProvider *dp) override {
        
            int i = dp->first();
            long long j = i;
            do
                j *= (i = dp->next(i));
            while(i != dp->last());
            return j;
        }
    };
    
    int main() {
        
        struct MyDataProvider : virtual public IDataProvider {
        
            int first() override {
         return 1; }
            int last() override {
         return 20; }
            int next(int v) override {
         return v+1; }
        };
        Foo foo(std::make_shared<MyDataProvider>(), std::make_shared<MultiplyAccumulateCalculator>(), std::make_shared<DefaultSerializer>(), std::make_shared<StreamPrinter>(std::cout));
        foo.run();
    }

提前优化的并行版本：

#include <iostream>
    #include <xmmintrin.h>
    
    double foo(int x) {
        
        __m128 a = {
        1.0f, 2.0f, 3.0f, 4.0f};
        __m128 b = {
        4.0f, 4.0f, 4.0f, 4.0f};
        __m128 c = {
        1.0f, 1.0f, 1.0f, 1.0f};
        for(int i = 0; i < x / 4; ++i, a = _mm_add_ps(a, b))
            c = _mm_mul_ps(c, a);
        for(int i = x % 4; i < 4; ++i)
            a[i] = 1.0f;
        c = _mm_mul_ps(c, a);
        return (double)c[0] * (double)c[1] * (double)c[2] * (double)c[3];
    }
    
    int main() {
        
        std::cout << foo(20) << std::endl;
    }

“宏孩儿”元编程版：

#include <boost/preprocessor.hpp>
    
    // 由于boost.preprocessor仅提供255以下的整数运算
    // 所以使用sequence来 (十位个位)(千位百位)(十万位万位) 的方式来表示大整数。
    
    // 不进位加法：(77)(66)(55) + (44)(33)(22) = (121)(99)(77)
    #define PP_ADD_N_N_CARRY_OP(R, DATA, I, ELEM) (BOOST_PP_ADD(BOOST_PP_SEQ_ELEM(I, DATA), ELEM))
    #define PP_ADD_N_N_CARRY(SEQ_A, SEQ_B) BOOST_PP_SEQ_FOR_EACH_I(PP_ADD_N_N_CARRY_OP, SEQ_A, SEQ_B)
    
    // 进位加法：(121)(99)(77) = （21)(0)(78)
    // 注意SEQ_A的长度要比SEQ_B长
    #define PP_ADD_N_N_OP(S, STATE, ELEM_CARRY) \
        BOOST_PP_SEQ_PUSH_FRONT( \
                BOOST_PP_SEQ_REPLACE(STATE, 0, BOOST_PP_MOD(BOOST_PP_ADD(BOOST_PP_SEQ_HEAD(STATE), ELEM_CARRY), 100)), \
                BOOST_PP_DIV(BOOST_PP_ADD(BOOST_PP_SEQ_HEAD(STATE), ELEM_CARRY), 100) \
                )
    #define PP_ADD_N_N(SEQ_A, SEQ_B) BOOST_PP_SEQ_REVERSE(BOOST_PP_SEQ_FOLD_LEFT(PP_ADD_N_N_OP, BOOST_PP_SEQ_NIL(0), PP_ADD_N_N_CARRY(SEQ_A, SEQ_B)))
    
    // 没什么好说的，X*N = X+X+X+X+X+...+X
    #define PP_MUL_N_1_EXP_OP(Z, I, DATA) (DATA)
    #define PP_MUL_N_1_EXP(SEQ_N, N) BOOST_PP_REPEAT(N, PP_MUL_N_1_EXP_OP, SEQ_N)
    #define PP_MUL_N_1_MYOP(S, STATE, ITEM) PP_ADD_N_N(STATE, ITEM)
    #define PP_MUL_N_1_FWD(EXP) BOOST_PP_SEQ_FOLD_LEFT(PP_MUL_N_1_MYOP, BOOST_PP_SEQ_HEAD(EXP), BOOST_PP_SEQ_TAIL(EXP))
    #define PP_MUL_N_1(SEQ_N, N) PP_MUL_N_1_FWD(PP_MUL_N_1_EXP(SEQ_N, N))
    
    #define FACT5 PP_MUL_N_1(PP_MUL_N_1(PP_MUL_N_1(PP_MUL_N_1((1), 2), 3), 4), 5)
    #define FACT10 PP_MUL_N_1(PP_MUL_N_1(PP_MUL_N_1(PP_MUL_N_1(PP_MUL_N_1(FACT5, 6), 7), 8), 9), 10)
    #define FACT15 PP_MUL_N_1(PP_MUL_N_1(PP_MUL_N_1(PP_MUL_N_1(PP_MUL_N_1(FACT10, 11), 12), 13), 14), 15)
    #define FACT20 PP_MUL_N_1(PP_MUL_N_1(PP_MUL_N_1(PP_MUL_N_1(PP_MUL_N_1(FACT15, 16), 17), 18), 19), 20)
    #define FACT25 PP_MUL_N_1(PP_MUL_N_1(PP_MUL_N_1(PP_MUL_N_1(PP_MUL_N_1(FACT20, 21), 22), 23), 24), 25)
    
    static_assert(false, BOOST_PP_STRINGIZE(FACT10));

警告：目前只有Clang能算出FACT20，编译缓慢是十分正常的，请耐心等待。默认计算10的阶乘10!=3628800，期待输出：

error: static_assert failed "(0) (88) (62) (3) (0) (0) (0) (0) (0) (0)"

真·模板元编程版本（大整数）

#include <iostream>
    #include <iomanip>
    #include <type_traits>
    
    using BaseType_t = long long;
    constexpr BaseType_t lgBase = 9; // 注意10000*10000刚刚好小于int的取值范围
    constexpr BaseType_t Base = 1000000000; // 注意10000*10000刚刚好小于int的取值范围
    
    // 大整数的表示
    template<BaseType_t...I> struct BigInteger {
        
        using type = BigInteger;
    };
    
    // 连接
    template<class T1, class T2> struct BI_Cat;
    template<BaseType_t...I1, BaseType_t...I2> struct BI_Cat <BigInteger<I1...>, BigInteger<I2...>> : BigInteger<I1..., I2...> {
        };
    
    // 左移一个单元（即*Base）
    template<class T> struct BI_SHL;
    template<BaseType_t...I> struct BI_SHL<BigInteger<I...>> : BigInteger<I..., 0> {
        };
    
    // 去除开头的0
    template<class T> struct BI_Remove_Zeros : T {
        };
    template<BaseType_t...I> struct BI_Remove_Zeros<BigInteger<0, I...>> : BI_Remove_Zeros<BigInteger<I...>> {
        };
    
    // 填充0到N个单元
    template<int X, class IS> struct BI_Fill_Impl;
    template<int X, class T, T...I> struct BI_Fill_Impl<X, std::integer_sequence<T, I...>> : BigInteger<(I, X)...> {
        };
    template<int Size> struct BI_Fill_Zeros : BI_Fill_Impl<0, std::make_index_sequence<Size>> {
        };
    
    template<class T, int N> struct BI_Resize;
    template<BaseType_t...I, int N> struct BI_Resize<BigInteger<I...>, N> : BI_Cat<typename BI_Fill_Zeros<N - sizeof...(I)>::type, BigInteger<I...>> {
        };
    
    // 返回较大的数值
    template<int A, int B> struct int_min : std::integral_constant<int, (A<B?B:A)> {
        };
    
    // 非进位加法：先把两个数的位数改成一样的然后依次相加
    template<class A, class B, class ShouldResize> struct BI_AddNotCarry_Impl;
    template<BaseType_t...I1, BaseType_t...I2> struct BI_AddNotCarry_Impl <BigInteger<I1...>, BigInteger<I2...>, std::true_type> : BigInteger<(I1 + I2)...> {
        };
    
    template<BaseType_t...I1, BaseType_t...I2> struct BI_AddNotCarry_Impl <BigInteger<I1...>, BigInteger<I2...>, std::false_type>
         : BI_AddNotCarry_Impl<
             typename BI_Resize<BigInteger<I1...>, int_min<sizeof...(I1), sizeof...(I2)>::value>::type,
             typename BI_Resize<BigInteger<I2...>, int_min<sizeof...(I1), sizeof...(I2)>::value>::type,
             std::true_type
         >{
        };
    
    template<class A, class B> struct BI_AddNotCarry;
    template<BaseType_t...I1, BaseType_t...I2> struct BI_AddNotCarry <BigInteger<I1...>, BigInteger<I2...>>
        : BI_AddNotCarry_Impl<BigInteger<I1...>, BigInteger<I2...>, std::bool_constant<sizeof...(I1) == sizeof...(I2)>> {
        };
    
    // 判断是否为0
    template<class Y> struct BI_IsZero;
    template<BaseType_t...I> struct BI_IsZero<BigInteger<I...>> : std::bool_constant<((I == 0) && ...)> {
        };
    
    // 自动进位
    template<class A> struct BI_Carry;
    template<class A, class B> struct BI_Add : BI_Carry<typename BI_AddNotCarry<A, B>::type> {
        };
    
    template<class Mod, class Div, class ShouldCalc = typename BI_IsZero<Div>::type> struct BI_Carry_Impl;
    template<class Mod, class Div> struct BI_Carry_Impl<Mod, Div, std::true_type> : Mod {
        };
    template<class Mod, class Div> struct BI_Carry_Impl<Mod, Div, std::false_type>
            : BI_Add<Mod, typename BI_SHL<Div>::type > {
        };
    template<BaseType_t...I> struct BI_Carry<BigInteger<I...>>
            : BI_Remove_Zeros<typename BI_Carry_Impl<BigInteger<(I % Base)...>, BigInteger<(I / Base)...>>::type> {
        };
    
    // 乘以X并自动进位
    template<class A, int X> struct BI_MulX;
    template<BaseType_t...I1, int X> struct BI_MulX <BigInteger<I1...>, X>
            : BI_Carry<BigInteger<(I1 * X)...>> {
        };
    
    // 计算阶乘
    template<int X> struct BI_Fact : BI_MulX<typename BI_Fact<X-1>::type, X> {
        };
    template<> struct BI_Fact<0> : BigInteger<1> {
        };
    
    template<BaseType_t...I>
    std::ostream &operator<<(std::ostream &out, BigInteger<I...>) {
        
        return ((out << std::setfill('0') << I << std::setw(lgBase)), ...);
    }
    
    int main()
    {
        
        std::cout << typename BI_Fact<20>::type() << std::endl;
    }

如果将BI\_Fact<20>改为BI\_Fact<1000>后，我们可爱的Clang解释器花了3秒多的时间很偷税地算出来了1000! =

> 402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

无人值守自动迭代版本

#include <iostream>
    #include <numeric>
    #include <vector>
    #include <functional>
    int main() {
        
    	std::vector<int> v(std::atoi(std::end(__DATE__) - (__LINE__) / 2)); // 2020年，第六行
    	std::iota(v.begin(), v.end(), 1);
    	std::cout << std::accumulate(v.begin(), v.end(), 1ull, std::multiplies<>()) << std::endl;
    }