[C言語] 小町算の実装方法とアルゴリズム解説

#include <stdio.h>
// 数字と演算子の組み合わせを試す関数
int tryCombination(int numbers[], char operators[], int target, int index, int current) {
    if (index == 4) { // すべての数字を使い切った場合
        return current == target;
    }
    // 次の数字を選択
    int nextNumber = numbers[index];
    
    // 各演算子を試す
    for (int i = 0; i < 4; i++) {
        char op = operators[i];
        int newCurrent = current;
        
        // 演算を実行
        switch (op) {
            case '+': newCurrent += nextNumber; break;
            case '-': newCurrent -= nextNumber; break;
            case '*': newCurrent *= nextNumber; break;
            case '/': if (nextNumber != 0) newCurrent /= nextNumber; break;
        }
        
        // 再帰的に次の組み合わせを試す
        if (tryCombination(numbers, operators, target, index + 1, newCurrent)) {
            return 1;
        }
    }
    return 0;
}
int main() {
    int numbers[] = {1, 2, 3, 4}; // 使用する数字
    char operators[] = {'+', '-', '*', '/'}; // 使用する演算子
    int target = 10; // 目標の数値
    if (tryCombination(numbers, operators, target, 1, numbers[0])) {
        printf("解が見つかりました。\n");
    } else {
        printf("解が見つかりませんでした。\n");
    }
    return 0;
}

#include <stdio.h>
void generatePermutations(int numbers[], int start, int end) {
    if (start == end) {
        // 数字の組み合わせを表示
        for (int i = 0; i <= end; i++) {
            printf("%d ", numbers[i]);
        }
        printf("\n");
    } else {
        for (int i = start; i <= end; i++) {
            // 数字を交換
            int temp = numbers[start];
            numbers[start] = numbers[i];
            numbers[i] = temp;
            // 再帰的に次の組み合わせを生成
            generatePermutations(numbers, start + 1, end);
            // 元に戻す
            temp = numbers[start];
            numbers[start] = numbers[i];
            numbers[i] = temp;
        }
    }
}
int main() {
    int numbers[] = {1, 2, 3, 4};
    generatePermutations(numbers, 0, 3);
    return 0;
}

#include <stdio.h>
int applyOperator(int a, int b, char op) {
    switch (op) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/': return (b != 0) ? a / b : 0; // 0除算を避ける
        default: return 0;
    }
}
void tryOperators(int numbers[], char operators[], int index, int current) {
    if (index == 4) {
        printf("計算結果: %d\n", current);
        return;
    }
    for (int i = 0; i < 4; i++) {
        int newCurrent = applyOperator(current, numbers[index], operators[i]);
        tryOperators(numbers, operators, index + 1, newCurrent);
    }
}
int main() {
    int numbers[] = {1, 2, 3, 4};
    char operators[] = {'+', '-', '*', '/'};
    tryOperators(numbers, operators, 1, numbers[0]);
    return 0;
}

#include <stdio.h>
int tryCombination(int numbers[], char operators[], int target, int index, int current) {
    if (index == 4) {
        return current == target;
    }
    for (int i = 0; i < 4; i++) {
        int newCurrent = applyOperator(current, numbers[index], operators[i]);
        if (tryCombination(numbers, operators, target, index + 1, newCurrent)) {
            return 1;
        }
    }
    return 0;
}
int main() {
    int numbers[] = {1, 2, 3, 4};
    char operators[] = {'+', '-', '*', '/'};
    int target = 10;
    if (tryCombination(numbers, operators, target, 1, numbers[0])) {
        printf("解が見つかりました。\n");
    } else {
        printf("解が見つかりませんでした。\n");
    }
    return 0;
}

#include <stdio.h>
// 演算子を適用する関数
int applyOperator(int a, int b, char op) {
    switch (op) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/': return (b != 0) ? a / b : 0; // 0除算を避ける
        default: return 0;
    }
}
// 数字と演算子の組み合わせを試す関数
int tryCombination(int numbers[], char operators[], int target, int index, int current) {
    if (index == 4) { // すべての数字を使い切った場合
        return current == target;
    }
    // 各演算子を試す
    for (int i = 0; i < 4; i++) {
        int newCurrent = applyOperator(current, numbers[index], operators[i]);
        if (tryCombination(numbers, operators, target, index + 1, newCurrent)) {
            return 1;
        }
    }
    return 0;
}
int main() {
    int numbers[] = {1, 2, 3, 4}; // 使用する数字
    char operators[] = {'+', '-', '*', '/'}; // 使用する演算子
    int target = 10; // 目標の数値
    if (tryCombination(numbers, operators, target, 1, numbers[0])) {
        printf("解が見つかりました。\n");
    } else {
        printf("解が見つかりませんでした。\n");
    }
    return 0;
}

解が見つかりました。