tax_game_bruteforce.c

#include <stdio.h>
#include <limits.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>

#define MAX 100
#define MIN 1

int PRIME[MAX] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
int NUM[MAX] = {};
int test_num;
int final_ans;
int final_order[MAX] = {};

int find_max_factor(int x) {
  int prime_idx = 0;
  while (PRIME[prime_idx] <= x) {
    if (x % PRIME[prime_idx]) {
      prime_idx++;
    } else {
      int max_fac = x / PRIME[prime_idx];
      if (NUM[max_fac]) {
        return max_fac;
      } else {
        prime_idx++;
      }
    }
  }

  if (NUM[1]) {
    return 1;
  }

  return x;
}

int min(int a, int b) {
  return a < b ? a : b;
}

void recursive(int depth, int used, int ans, int order[]) {
  if (used == 0) {

    //printf("ans: %d\norder:", ans);
    /*
    for(size_t idx = 0; order[idx] != 0; ++idx) {
      printf("%d ", order[idx]);
    }
    printf("\n");
    */
    if (ans < final_ans) {
      memcpy(final_order, order, sizeof(int) * depth);
      final_ans = ans;
    }
    //exit(0);
    return;
  }
  //printf("depth: %d, used: %d\n", depth, used);

  for (int idx = test_num; idx > 0; --idx) {
    if (!NUM[idx]){
      continue;
    } else {
      int factor = find_max_factor(idx);
      if (ans + factor >= final_ans) {
        continue;
      }
      order[depth] = idx;
      NUM[factor] = 0;
      NUM[idx] = 0;
      ans += factor;
      int new_used = used - 1 - (!(factor == idx));
      recursive(depth+1, new_used, ans, order);
      ans -= factor;
      NUM[idx] = 1;
      NUM[factor] = 1;
      order[depth] = 0;
    }
  }
  return;
}

int main() {
  fprintf(stdout, "What number do you want to test? (%d ~ %d) ", MIN, MAX);
  fscanf(stdin, "%d", &test_num);

  if (test_num > MAX || test_num < MIN) {
    fprintf(stdout, "Input(%d) number is out of range! (%d ~ %d)", test_num, MIN, MAX);
    return 0;
  }

  // Initialize (Set NUM to unused)
  for (int idx = 1; idx <= test_num; ++idx) {
    NUM[idx] = 1;
    final_order[idx] = 0;
  }
  final_ans = INT_MAX;

  time_t before = time(NULL);
  int order[MAX] = {};
  recursive(0, test_num, 0, order);
  fprintf(stdout, "Used time: %ld sec\n", time(NULL) - before);

  final_ans = test_num * (test_num+1) / 2 - final_ans;
  fprintf(stdout, "Ans: %d\norder: ", final_ans);
  for(size_t idx = 0; final_order[idx] != 0; ++idx) {
    fprintf(stdout, "%d ", final_order[idx]);
  }
  fprintf(stdout, "\n");
  return 0;
}

假設要測的數字是 n
所需的時間會是 n!/10^7 sec
=> 15 以上就要跑很久了

╭─calee@workstation ~/junior/mine
╰─➤ echo 1 | ./a.out 1 ↵
What number do you want to test? (1 ~ 100) Used time: 0 sec
Ans: 1
order: 1
╭─calee@workstation ~/junior/mine
╰─➤ echo 2 | ./a.out
What number do you want to test? (1 ~ 100) Used time: 0 sec
Ans: 1
order: 2
╭─calee@workstation ~/junior/mine
╰─➤ echo 3 | ./a.out
What number do you want to test? (1 ~ 100) Used time: 0 sec
Ans: 3
order: 3 2
╭─calee@workstation ~/junior/mine
╰─➤ echo 4 | ./a.out
What number do you want to test? (1 ~ 100) Used time: 0 sec
Ans: 3
order: 4 3
╭─calee@workstation ~/junior/mine
╰─➤ echo 5 | ./a.out
What number do you want to test? (1 ~ 100) Used time: 0 sec
Ans: 6
order: 5 4 3
╭─calee@workstation ~/junior/mine
╰─➤ echo 6 | ./a.out
What number do you want to test? (1 ~ 100) Used time: 0 sec
Ans: 6
order: 6 5 4
╭─calee@workstation ~/junior/mine
╰─➤ echo 7 | ./a.out
What number do you want to test? (1 ~ 100) Used time: 0 sec
Ans: 11
order: 7 6 5 4
╭─calee@workstation ~/junior/mine
╰─➤ echo 8 | ./a.out
What number do you want to test? (1 ~ 100) Used time: 0 sec
Ans: 15
order: 8 7 6 5 2
╭─calee@workstation ~/junior/mine
╰─➤ echo 9 | ./a.out
What number do you want to test? (1 ~ 100) Used time: 0 sec
Ans: 21
order: 9 8 7 6 5 2
╭─calee@workstation ~/junior/mine
╰─➤ echo 10 | ./a.out
What number do you want to test? (1 ~ 100) Used time: 0 sec
Ans: 21
order: 10 9 8 7 6 2
╭─calee@workstation ~/junior/mine
╰─➤ echo 11 | ./a.out
What number do you want to test? (1 ~ 100) Used time: 0 sec
Ans: 28
order: 11 10 9 8 7 6 2
╭─calee@workstation ~/junior/mine
╰─➤ echo 12 | ./a.out
What number do you want to test? (1 ~ 100) Used time: 0 sec
Ans: 28
order: 12 11 10 9 8 7 2
╭─calee@workstation ~/junior/mine
╰─➤ echo 13 | ./a.out
What number do you want to test? (1 ~ 100) Used time: 3 sec
Ans: 39
order: 13 12 11 10 9 8 7 2
╭─calee@workstation ~/junior/mine
╰─➤ echo 14 | ./a.out
What number do you want to test? (1 ~ 100) Used time: 20 sec
Ans: 39
order: 14 13 12 11 10 9 8 2

╭─calee@workstation ~/junior/mine
╰─➤ echo 15 | ./a.out
What number do you want to test? (1 ~ 100) Used time: 192 sec
Ans: 49
order: 15 14 13 12 11 10 9 8 2

╭─calee@workstation ~/junior/mine
╰─➤ ./a.out
What number do you want to test? (1 ~ 100) 20
Used time: 0 sec
Ans: 92
order: 20 19 18 17 16 15 14 13 12 11 4 3
╭─calee@workstation ~/junior/mine
╰─➤ ./a.out
What number do you want to test? (1 ~ 100) 21
Used time: 3 sec
Ans: 106
order: 21 20 19 18 17 16 15 14 13 12 11 4 3
╭─calee@workstation ~/junior/mine
╰─➤ ./a.out
What number do you want to test? (1 ~ 100) 22
Used time: 1 sec
Ans: 106
order: 22 21 20 19 18 17 16 15 14 13 12 4 3
╭─calee@workstation ~/junior/mine
╰─➤ ./a.out
What number do you want to test? (1 ~ 100) 23
Used time: 15 sec
Ans: 125
order: 23 22 21 20 19 18 17 16 15 14 13 12 4 3
╭─calee@workstation ~/junior/mine
╰─➤ ./a.out
What number do you want to test? (1 ~ 100) 24
Used time: 14 sec
Ans: 131
order: 24 23 22 21 20 19 18 17 16 15 14 13 6 4
╭─calee@workstation ~/junior/mine
╰─➤ ./a.out
What number do you want to test? (1 ~ 100) 25
Used time: 124 sec
Ans: 146
order: 25 24 23 22 21 20 19 18 17 16 15 14 13 6 4