算法趣題-Q10

一、問題描述

二、問題分析

        這個就是循環求和，比較容易暴擊求解（Python實作），當然也可以進行一些優化，減少計算次數，如使用數組進行疊代求和（C/C++實作）。

三、代碼實作

1.C/C++實作

#include <iostream>
#define MAX_N 36
#define MIN_N 2
#define ARRAY_SIZE 40

using namespace std;

// 37 個數
int erule[] = { 0, 32, 15, 19, 4, 21, 2, 25, 17,
                34, 6, 27, 13, 36, 11, 30, 8, 23,
                10, 5, 24, 16, 33, 1, 20, 14, 31,
                9, 22, 18, 29, 7, 28, 12, 35, 3, 26 };

// 38 個數
int urule[] = { 0, 28, 9, 26, 30, 11, 7, 20, 32,
                17, 5, 22, 34, 15, 3, 24, 36, 13,
                1, 0, 27, 10, 25, 29, 12, 8, 19,
                31, 18, 6, 21, 33, 16, 4, 23, 35, 14, 2 };

void calc(const int rule[], int size, int result[MAX_N])
{
    memset(result, 0, sizeof(result));
    // 矩陣 temp 用于疊代
    int temp[ARRAY_SIZE];
    for (int i = 0; i < size; i++)
    {
        temp[i] = rule[i];
    }
    // 根據步長進行疊代
    for (int step = 1; step < MAX_N; step++)
    {
        int max = 0;
        for (int j = 0; j < size; j++)
        {
            temp[j] += rule[(j + step) % size];
            if (temp[j] > max)
            {
                max = temp[j];
            }
        }
        result[step] = max;
    }
    
    return;
}

int main()
{
    int eresult[MAX_N];
    int uresult[MAX_N];
    calc(erule, 37, eresult);
    calc(urule, 38, uresult);
    int count = 0;
    for (int i = MIN_N - 1; i < MAX_N; i++)
    {
        if (eresult[i] < uresult[i])
        {
            count++;
        }
    }
    cout << count << endl;
    return 0;
}
           

2.Python實作

# coding=utf-8

e_rule = [0, 32, 15, 19, 4, 21, 2, 25, 17,
          34, 6, 27, 13, 36, 11, 30, 8, 23,
          10, 5, 24, 16, 33, 1, 20, 14, 31,
          9, 22, 18, 29, 7, 28, 12, 35, 3, 26]

u_rule = [0, 28, 9, 26, 30, 11, 7, 20, 32,
          17, 5, 22, 34, 15, 3, 24, 36, 13,
          1, 0, 27, 10, 25, 29, 12, 8, 19,
          31, 18, 6, 21, 33, 16, 4, 23, 35, 14, 2]


def calc(rule, min_n, max_n):
    n_max = []
    len_rule = len(rule)
    for n in range(min_n, max_n + 1):
        max_sum = 0
        for i in range(len_rule):
            if i + n < len_rule:
                temp = sum(rule[i:i + n])
            else:
                temp = sum(rule[i:]) + sum(rule[:(i + n) % len_rule])
            if temp > max_sum:
                max_sum = temp
        n_max.append(max_sum)
    return tuple(n_max)


if __name__ == '__main__':
    e_re = calc(e_rule, 2, 36)
    u_re = calc(u_rule, 2, 36)
    count = 0
    for i in range(36 - 2 + 1):
        if e_re[i] < u_re[i]:
            count += 1
    print(count)