#include <stdio.h> #include <stdlib.h> #include <stdbool.h>
#define SIZE 8 #define DIGITS 10
#define D 0 #define E 1 #define Y 2 #define N 3 #define R 4 #define O 5 #define S 6 #define M 7 #define CONTINUE 2 #define GOOD 0 #define BAD 1 /* SEND + MORE -------- MONEY -------- */
int singleVerify2(int code[SIZE], int *CARRY){ if(code[D] == -1) return CONTINUE; if(code[E] == -1) return CONTINUE; if(code[Y] == -1) return CONTINUE; int singleSum = code[D] + code[E]; if(singleSum > DIGITS) *CARRY = 1; else *CARRY = 0; if(singleSum % DIGITS == code[Y]) return GOOD; else return BAD; } /* SEND + MORE -------- MONEY -------- */ int tenVerify2(int code[SIZE], int *CARRY){ if(code[N] == -1) return CONTINUE; if(code[R] == -1) return CONTINUE; if(code[E] == -1) return CONTINUE; int tenSum = code[N] + code[R] + *CARRY; if(tenSum > DIGITS) *CARRY = 1; else *CARRY = 0; if(tenSum % DIGITS == code[E]) return GOOD; else return BAD; }
/* SEND + MORE -------- MONEY -------- */ int hundredVerify2(int code[SIZE], int *CARRY){ if(code[E] == -1) return CONTINUE; if(code[O] == -1) return CONTINUE; if(code[N] == -1) return CONTINUE; int hundredSum = code[E] + code[O] + *CARRY; if(hundredSum > DIGITS) *CARRY = 1; else *CARRY = 0; if(hundredSum % DIGITS == code[N]) return GOOD; else return BAD; } /* SEND + MORE -------- MONEY -------- */ int thousandVerify2(int code[SIZE], int *CARRY){ if(code[S] == -1) return CONTINUE; if(code[M] == -1) return CONTINUE; if(code[O] == -1) return CONTINUE; if(code[M] == -1) return CONTINUE; int thousandSum = code[S] + code[M] + *CARRY; if(thousandSum == code[M] * DIGITS + code[O]) return GOOD; else return BAD; } bool exhaustive2(int code[SIZE],int codeIndex, int digits[DIGITS]){ for(int i = 0 ; i < DIGITS; i++){ if(digits[i] == -1) continue; int middle = digits[i]; code[codeIndex] = middle; digits[i] = -1; int CARRY_ ,*CARRY; CARRY_ = 0; CARRY = &CARRY_; //first single position Verify int state = singleVerify2(code, CARRY); if(state == CONTINUE){ if(exhaustive2(code, codeIndex + 1, digits)) return true; else{ code[codeIndex] = -1; digits[i] = middle; continue; } }else if(state == BAD){ code[codeIndex] = -1; digits[i] = middle; continue; } //second ten position Verify state = tenVerify2(code, CARRY); if(state == CONTINUE){ if(exhaustive2(code, codeIndex + 1, digits)) return true; else{ code[codeIndex] = -1; digits[i] = middle; continue; } }else if(state == BAD){ code[codeIndex] = -1; digits[i] = middle; continue; } //third hundred position Verify state = hundredVerify2(code, CARRY); if(state == CONTINUE){ if(exhaustive2(code, codeIndex + 1, digits)) return true; else{ code[codeIndex] = -1; digits[i] = middle; continue; } }else if(state == BAD){ code[codeIndex] = -1; digits[i] = middle; continue; } //fourth thousand position Verify state = thousandVerify2(code, CARRY); if(state == CONTINUE){ if(exhaustive2(code, codeIndex + 1, digits)) return true; else{ code[codeIndex] = -1; digits[i] = middle; continue; } }else if(state == BAD){ code[codeIndex] = -1; digits[i] = middle; continue; } return true; } return false; }
void printCryptarithmetic2(char *str, int code[SIZE]){ for(int i = 0; i < SIZE; i++){ printf("%5c %5d\n",*str++, code[i]); } }
int main(){ //char *str = {'0D', '1E', '2Y', '3N', '4R', '5O', '6S', '7M'}; char str[] = {'D', 'E', 'Y', 'N', 'R', 'O', 'S', 'M'}; int digits[DIGITS] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; int code[SIZE] = {-1, -1, -1, -1, -1, -1, -1, -1}; if(exhaustive2(code, 0, digits)) printCryptarithmetic2(str, code); return 0; }
优化后
#include <stdio.h> #include <stdlib.h> #include <stdbool.h>
#define SIZE 8 #define DECIMAL 10 #define POSITION_NUM 13
#define CONTINUE 1 #define RETRY 0 #define D 0 #define E 1 #define Y 2 #define N 3 #define R 4 #define O 5 #define S 6 #define M 7 /* SEND + MORE -------- MONEY -------- */ //char str[] = {'D', 'E', 'Y', 'N', 'R', 'O', 'S', 'M'}; int** initPositions(int code[SIZE]){ int *positions[POSITION_NUM]; positions[0] = &code[D]; positions[1] = &code[E]; positions[2] = &code[Y]; positions[3] = &code[N]; positions[4] = &code[R]; positions[5] = &code[E]; positions[6] = &code[E]; positions[7] = &code[O]; positions[8] = &code[N]; positions[9] = &code[S]; positions[10] = &code[M]; positions[11] = &code[O]; positions[12] = &code[M]; return positions; }
//打印解决方案 void printCryptarithmetic(int code[SIZE]){ char str[] = {'D', 'E', 'Y', 'N', 'R', 'O', 'S', 'M'}; for(int i = 0; i < SIZE; i++){ printf("%5c %5d\n", str[i], code[i]); } printf("==========================\n"); } //加法器 int adder(int code[SIZE]){ int carry = 0; int **positions = initPositions(code); for(int j = 0; j < POSITION_NUM; j++){ //第j位的code未赋值，继续 赋值 if(*positions[j] == -1) return CONTINUE; //如果是加数，继续赋值 int index = (j + 1) % 3; if(index > 0) continue; //求和 int sum = *positions[j - 2] + *positions[j - 1] + carry; if(sum >= DECIMAL) carry = 1; else carry = 0; if(sum % DECIMAL == *positions[j]) continue ; else return RETRY; } //加数的位数 + 被加数的位数 + 和的位数 //为偶数（没有进位） if(POSITION_NUM % 2 == 0){ printCryptarithmetic(code); return RETRY; } /* SEND + MORE -------- MONEY -------- */ //为奇数，最高位的值与进位相等 if(code[SIZE - 1] == carry) printCryptarithmetic(code); return RETRY; } // void exhaustively(int code[SIZE], int codeIndex, int digits[DECIMAL]){ for(int i = 0 ; i < DECIMAL; i++){ if(digits[i] == -1) continue; int middle = digits[i]; code[codeIndex] = middle; digits[i] = -1; if(adder(code)) exhaustively(code, codeIndex + 1, digits); code[codeIndex] = -1; digits[i] = middle; } }
int main12(){ int digits[DECIMAL] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; int code[SIZE] = {-1, -1, -1, -1, -1, -1, -1, -1}; exhaustively(code, 0, digits); return 0; }
