2 つの条件を持つ数値を生成する小さなプログラムを作成しました。
- 1 から 9 までのすべての数字があるため、123456789 のような数字になります
- 4 % 2 == 0 および 4 % 4 == 0 であるため、数値は最後の桁で割り切れる必要があります (例: 442)。
これは私のバックトラックアルゴリズムです:
static void backTrack(int value)
{
//Check if the number has all 9 digits, that it is dividable
if(isNine(value) && isDiv(value))
{
//System.out.println(value);
System.out.println("Found solution.");
System.out.println(aantal);
aantal++;
}
else
{
if(howMany(value) >= 9)
return;
for(int i = 1; i < 10; i++)
{
value = value * 10 + i;
if(value % i == 0 && howMany(value) <= 9)
{
//System.out.println(value);
backTrack(value);
}
value = value / 10;
}
}
}
//Gives length of integer for example 124 must give 3, 13 gives 2
static int howMany(int value)
{
int test = value % 10;
value = value / 10;
int teller = 0;
while(test != 0)
{
teller++;
test = value % 10;
value = value / 10;
}
return teller;
}
//Checks if the number is dividable by the last digit of the number and keeps recursive doing this for the whole number so 442 = YES 235 = NO
static boolean isDiv(int value)
{
int test = value % 10;
value = value / 10;
while(test != 0)
{
if(value % test == 0)
{
test = value % 10;
value = value / 10;
}
else
return false;
}
return true;
}
//Checks if the number has all digits from 1 to 9
static boolean isNine(int value)
{
boolean values[] = new boolean[10];
int test = value % 10;
int counter = 0;
for(int i = 1; i < values.length; i++)
values[i] = false;
while( test != 0)
{
if(values[test])
return false;
else
{
values[test] = true;
value = value /10;
test = value % 10;
}
}
for(int i = 1; i < values.length; i++)
{
if(values[i])
counter++;
}
if(counter == 9)
return true;
else
return false;
}
すべてのサブ機能をテストしましたが、それらはうまく機能しています。
バックトラッキング方式に何か問題がありますか? これSystem.out.println(aantal)は、私が見つけたソリューションの数をカウントするための変数です。
私はから始めますbacktrack(0);