次の暗号を解決するプログラムを C で作成しようとしています。
1 + 1 = 2
セブンが素数
9は完全な正方形です
つまり、単語one、two、Seven、nineの数値を見つける必要があります。ここで、各文字 (o、n、e、t、w、s、v、i) に数値が割り当てられ、完全な数も満たされます。上記のすべての条件。
私は、単語ごとにint配列を作成し、1）各単語が条件を満たしているかどうかを確認し（たとえば、「7」の素数である）、2）配列内の各整数が一致しているかどうかを確認するという方針に沿って考えていました他の単語の値で、他の単語もそれぞれの条件を満たしていることがわかります。
ただし、反復ごとに int 配列を単一の int に継続的に変換する必要があり、配列内の各要素を同時に他の単語と一致させる方法がわからないため、これが機能していることは実際にはわかりません。
おそらく、単語ごとに真でなければならない MIN と MAX の数値範囲を知っていると便利でしょうか?
何か案は？
力ずくの (ish) メソッドの場合、素数から始めて、エラトステネスのふるいsevenを使用して 99999 までのすべての素数を取得します。2 桁目と 4 桁目が同じでない場合は、すべての回答を破棄できます。 . その後、正方形に進むことができます。これは、3 桁の数字が素数によって決定されるためです。それは可能性をうまく絞り込むはずであり、@pmgの答えを使用してそれを終わらせることができます:-)。nineseven
更新：次のC＃プログラムがそれを行うようです
bool[] poss_for_seven = new bool[100000]; // this will hold the possibilities for `seven`
for (int seven = 0; seven < poss_for_seven.Length; seven++)
poss_for_seven[seven] = (seven > 9999); // `seven` must have 5 digits
// Sieve of Eratosthenes to make `seven` prime
for (int seven = 2; seven < poss_for_seven.Length; seven++) {
for (int j = 2 * seven; j < poss_for_seven.Length; j += seven) {
poss_for_seven[j] = false;
}
}
// look through the array poss_for_seven[], considering each possibility in turn
for (int seven = 10000; seven < poss_for_seven.Length; seven++) {
if (poss_for_seven[seven]) {
int second_digit = ((seven / 10) % 10);
int fourth_digit = ((seven / 1000) % 10);
if (second_digit == fourth_digit) {
int e = second_digit;
int n = (seven % 10); // NB: `n` can't be zero because otherwise `seven` wouldn't be prime
for (int i = 0; i < 10; i++) {
int nine = n * 1000 + i * 100 + n * 10 + e;
int poss_sqrt = (int)Math.Floor(Math.Sqrt(nine) + 0.1); // 0.1 in case of of rounding error
if (poss_sqrt * poss_sqrt == nine) {
int o = ((2 * e) % 10); // since 2 * `one` = `two`, we now know `o`
int one = o * 100 + n * 10 + e;
int two = 2 * one;
int t = ((two / 100) % 10);
int w = ((two / 10) % 10);
// turns out that `one`=236, `two`=472, `nine` = 3136.
// look for solutions where `s` != `v` with `s` and `v' different from `o`, `n`, `e`,`t`, `w` and `i`
int s = ((seven / 10000) % 10);
int v = ((seven / 100) % 10);
if (s != v && s != o && s != n && s != e && s != t && s != w && s != i && v != o && v != n && v != e && v != t && v != w && v != i) {
System.Diagnostics.Trace.WriteLine(seven + "," + nine + "," + one + "," + two);
}
}
}
}
}
}
nineは常に 3136 に等しいように見えるので、 one= 236 とtwo= 472 になります。ただし、 には 21 の可能性がありsevenます。2 つの数字が同じ値を取ることができないという制約を追加すると (これは上記の C# コードが行うことです)、可能性は 1 つだけになります (ただし、私のコードのバグにより、この回答には元々 3 つの可能性がありました)。
seven,nine,one,two
56963,3136,236,472
私はあなたの暗号を解決するためにacプログラムを構築する時間を見つけました。ブルートフォースプログラミングを開始する前に、数学的に問題に取り組むことで、出力の速度が大幅に向上すると思います。
いくつかの数学 (数論): ONE + ONE = TWO であるため、O は 4 より大きくなりません。ONE + ONE は 4 桁になるからです。また、O は 0 にはなりません。TWO は O で終わり、2 * ONE であるため偶数です。これら 3 つのフィルターを O に適用すると、可能な値は O= {2,4} のままです。したがって、(E+E) モジュラス 10 は = O でなければならないため、E は {1,2,6,7} になります。より具体的には、O=2 E={1,6} を含意し、O=4 は E={2,7} を含意する 次に、N をフィルター処理します。SEVEN が素数であることを考えると、N は奇数でなければなりません。また、5 で終わるものはすべて 5 で割り切れるため、N を 5 にすることはできません。したがって、N={1,3,7,9}
最も出現する文字 (O、E、N) の可能性を減らしたので、繰り返しを大幅に減らして、すべての残忍さでこのクリプタリスを攻撃する準備が整いました。
Cコードは次のとおりです。
#include <stdio.h>
#include <math.h>
#define O 0
#define N 1
#define E 2
#define T 3
#define W 4
#define S 5
#define V 6
#define I 7
bool isPerfectSquare(int number);
bool isPrime(int number);
void printSolutions(int countSolutions);
int filterNoRepeat(int unfilteredCount);
int solutions[1000][8]; // solution holder
int possibilitiesO[2] = {2,4};
int possibilitiesN[4] = {1,3,7,9};
int possibilitiesE[4] = {1,6,2,7};
void main() {
int countSolutions = 0;
int numberOne;
// iterate to fill up the solutions array by: one + one = two
for(int o=0;o<2;o++) {
for(int n=0;n<4;n++) {
for(int e=2*o;e<2*o+2;e++) { // following code is iterated 2*4*2 = 16 times
numberOne = 100*possibilitiesO[o] + 10*possibilitiesN[n] + possibilitiesE[e];
int w = ((2*numberOne)/10)%10;
int t = ((2*numberOne)/100)%10;
// check if NINE is a perfect square
for(int i=0;i<=9;i++) { // i can be anything ----- 10 iterations
int numberNine = 1000*possibilitiesN[n] + 100*i + 10*possibilitiesN[n] + possibilitiesE[e];
if(isPerfectSquare(numberNine)) {
// check if SEVEN is prime
for(int s=1;s<=9;s++) { // s cant be 0 ------ 9 iterations
for(int v=0;v<=9;v++) { // v can be anything other than s ------- 10 iterations
if(v==s) continue;
int numberSeven = 10000*s + 1000*possibilitiesE[e] + 100*v + 10*possibilitiesE[e] + possibilitiesN[n];
if(isPrime(numberSeven)) { // store solution
solutions[countSolutions][O] = possibilitiesO[o];
solutions[countSolutions][N] = possibilitiesN[n];
solutions[countSolutions][E] = possibilitiesE[e];
solutions[countSolutions][T] = t;
solutions[countSolutions][W] = w;
solutions[countSolutions][S] = s;
solutions[countSolutions][V] = v;
solutions[countSolutions][I] = i;
countSolutions++;
}
}
}
}
}
}
}
}
// 16 * 9 * 10 * 10 = 14400 iterations in the WORST scenario, conditions introduced reduce MOST of these iterations to 1 if() line
// iterations consumed by isPrime() function are not taken in count in the aproximation above.
// filter solutions so that no two letter have the same digit
countSolutions = filterNoRepeat(countSolutions);
printSolutions(countSolutions); // voila!
}
bool isPerfectSquare(int number) { // check if given number is a perfect square
double root = sqrt((double)number);
if(root==floor(root)) return true;
else return false;
}
bool isPrime(int number) { // simple algoritm to determine if given number is prime, check interval from sqrt(number) to number/2 with a step of +2
int startValue = sqrt((double)number);
if(startValue%2==0) startValue--; // make it odd
for(int k=startValue;k<number/2;k+=2) {
if(number%k==0) return false;
}
return true;
}
void printSolutions(int countSolutions) {
for(int k=0;k<countSolutions;k++) {
int one = 100*solutions[k][O] + 10*solutions[k][N] + solutions[k][E];
int two = 100*solutions[k][T] + 10*solutions[k][W] + solutions[k][O];
int seven = 10000*solutions[k][S] + 1000*solutions[k][E] + 100*solutions[k][V] + 10*solutions[k][E] + solutions[k][N];
int nine = 1000*solutions[k][N] + 100*solutions[k][I] + 10*solutions[k][N] + solutions[k][E];
printf("ONE: %d, TWO: %d, SEVEN: %d, NINE %d\n",one,two,seven,nine);
}
}
int filterNoRepeat(int unfilteredCount) {
int nrSol = 0;
for(int k=0;k<unfilteredCount;k++) {
bool isValid = true;
for(int i=0;i<7;i++) { // if two letters match, solution is not valid
for(int j=i+1;j<8;j++) {
if(solutions[k][i]==solutions[k][j]) {
isValid = false;
break;
}
}
if(!isValid) break;
}
if(isValid) { // store solution
for(int i=0;i<8;i++) {
solutions[nrSol][i] = solutions[k][i];
}
nrSol++;
}
}
return nrSol;
}
これにまだ興味がある場合は、自分でコードを試すことができます:P. 結果は 1 つのソリューションです。ONE: 236、TWO: 472、SEVEN: 56963、NINE: 3136 このソリューションは確率論のソリューションと同じであり、両方のアルゴリズムの正しさを確認しています:)。この素敵な暗号を提供してくれてありがとう。良い一日を！
ブルートフォースFTW！
#define ONE ((o*100) + (n*10) + e)
#define TWO ((t*100) + (w*10) + o)
#define SEVEN ((s*10000) + (e*1010) + (v*100) + n)
#define NINE ((n*1010) + (i*100) + e)
for (o = 1; o < 10; o++) { /* 1st digit cannot be zero (one) */
for (n = 1; n < 10; n++) { /* 1st digit cannot be zero (nine) */
if (n == o) continue;
for (e = 0; n < 10; n++) {
if (e == n) continue;
if (e == o) continue;
/* ... */
if (ONE + ONE == TWO) /* whatever */;
/* ... */
}
}
}