Last active
September 6, 2021 14:54
-
-
Save ochaochaocha3/514d3a4df152dda8e61c1a2c9ca7af4a to your computer and use it in GitHub Desktop.
オークの問題C言語版
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
orcs: orcs.c | |
$(CC) -std=gnu11 -o $@ $^ |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* https://twitter.com/MomiRaccoon/status/1434402973627531267 | |
* | |
* 女騎士「わ、私に性感度3000倍もさせて一体何をさせるんだ…」 | |
* オーク「ククク…」 | |
* | |
* オークA「感度を半分にするクスリだ」 | |
* オークB「感度を900マイナスにするクスリだ」 | |
* オークC「感度を2000プラスにするクスリだ」 | |
* オークD「感度を5倍するクスリだ」 | |
* オークE「感度を500プラスにするクスリだ」 | |
* | |
* 女騎士「はじめの感度の値が0であった場合、感度の値を3000にするためにオーク達はどんな順序でクスリを飲ませることになるんだ…!?」 | |
*/ | |
#include <stdio.h> | |
/** オークを表す構造体。 */ | |
typedef struct Orc_t { | |
/** 名前。 */ | |
char name; | |
/** クスリを投与する。投与後の感度を返す。 */ | |
int (*medicate)(int sensitivity); | |
} Orc; | |
/** 順列に対する処理の関数の型。 */ | |
typedef void (*EachPermutationProc)(Orc * const *, size_t); | |
/** | |
* @brief すべての順列をイテレートする。 | |
* @param orcs オークへのポインタの配列。 | |
* @param n 要素数。 | |
* @param proc 順列に対する処理。 | |
*/ | |
void each_permutation(Orc** orcs, size_t n, EachPermutationProc proc); | |
/** | |
* @brief Heapのアルゴリズムですべての順列をイテレートする(再帰処理)。 | |
* @param orcs オークへのポインタの配列。 | |
* @param n 要素数。 | |
* @param k カウンタ。最初はnとすること。 | |
* @param proc 順列に対する処理。 | |
*/ | |
void each_permutation_iter(Orc** orcs, size_t n, size_t k, EachPermutationProc proc); | |
/** 2つのオークへのポインタを交換する。 */ | |
void swap_orcs(Orc** a, Orc** b); | |
/** | |
* @brief 感度の計算結果が3000となったときに順序を出力する。 | |
* @param orcs オークへのポインタの配列。 | |
* @param n 要素数。 | |
*/ | |
void output_order_if_sensitivity_gets_3000(Orc * const * orcs, size_t n); | |
/** オークA「感度を半分にするクスリだ」 */ | |
int orc_a_medicate(int sensitivity) { return sensitivity / 2; } | |
/** オークB「感度を900マイナスにするクスリだ」 */ | |
int orc_b_medicate(int sensitivity) { return sensitivity - 900; } | |
/** オークC「感度を2000プラスにするクスリだ」 */ | |
int orc_c_medicate(int sensitivity) { return sensitivity + 2000; } | |
/** オークD「感度を5倍するクスリだ」 */ | |
int orc_d_medicate(int sensitivity) { return 5 * sensitivity; } | |
/** オークE「感度を500プラスにするクスリだ」 */ | |
int orc_e_medicate(int sensitivity) { return sensitivity + 500; } | |
int main(void) { | |
Orc orc_a = {'A', orc_a_medicate}; | |
Orc orc_b = {'B', orc_b_medicate}; | |
Orc orc_c = {'C', orc_c_medicate}; | |
Orc orc_d = {'D', orc_d_medicate}; | |
Orc orc_e = {'E', orc_e_medicate}; | |
Orc* orcs[] = {&orc_a, &orc_b, &orc_c, &orc_d, &orc_e}; | |
const size_t n = sizeof(orcs) / sizeof(orcs[0]); | |
each_permutation(orcs, n, output_order_if_sensitivity_gets_3000); | |
return 0; | |
} | |
void output_order_if_sensitivity_gets_3000(Orc * const * orcs, size_t n) { | |
int sensitivity = 0; | |
for (size_t i = 0; i < n; i++) { | |
sensitivity = orcs[i]->medicate(sensitivity); | |
} | |
if (sensitivity != 3000) { | |
return; | |
} | |
for (size_t i = 0; i < n; i++) { | |
if (i > 0) { | |
fputs("->", stdout); | |
} | |
putchar(orcs[i]->name); | |
} | |
putchar('\n'); | |
} | |
void each_permutation(Orc** orcs, size_t n, EachPermutationProc proc) { | |
each_permutation_iter(orcs, n, n, proc); | |
} | |
void each_permutation_iter(Orc** orcs, size_t n, size_t k, EachPermutationProc proc) { | |
if (k == 1) { | |
proc(orcs, n); | |
return; | |
} | |
for (size_t i = 0; i < k; i++) { | |
each_permutation_iter(orcs, n, k - 1, proc); | |
if (k & 1) { | |
swap_orcs(&orcs[0], &orcs[k - 1]); | |
} else { | |
swap_orcs(&orcs[i], &orcs[k - 1]); | |
} | |
} | |
} | |
void swap_orcs(Orc** a, Orc** b) { | |
Orc* temp = *a; | |
*a = *b; | |
*b = temp; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
C->A->B->E->D | |
C->A->E->B->D | |
B->C->D->E->A | |
C->B->D->E->A |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment