Нашел интересный алгоритм перебора, но так и не могу понять, как он работает. Пожалуйста, поясните.
public class TestNotMySort {
public static void main(String[] args) {
for (int r = 1; r <= 3 ; r++) {
proc(0, 1, r);
}
}
//рекурсивно перебираем все числа.
// numb - число старшего разряда
// first - наименьшая цифра для текущего разряда;
// digPos - ЧИСЛО РАЗРЯДОВ, текущий разряд, позиция цифры в числе;
private static void proc(long numb, int first, int digPos){
for (int i = first; i < 10; i++){
long number = i * pow(10, digPos - 1) + numb;
System.out.println(number + ": numb этого числа " + numb +", first этого числа - " + first +", digPos - "+ digPos);
if (digPos > 1) {
proc(number, i, digPos - 1);
};
}
}
// возведение в степень exp числа num
public static long pow (int num, int exp) {
long l = 1;
for (int i = 0; i < exp; i++)
l *= (long)num;
return l;
}
}
package com.javarush.task.task20.task2025;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
/*
Алгоритмы-числа
*/
public class Solution {
public static long[][] expArr; //матрица степеней чисел
/*
9 800 817,
24 678 050,
4 679 307 774 - ПОЧЕМУ-ТО НЕ НАХОДИТ ЭТИ ЧИСЛА
*/
public static void main(String[] args) {
Long t1 = System.currentTimeMillis();
long [] result1 = getNumbers(4679307775L);
Long t11 = System.currentTimeMillis();
System.out.println(Arrays.toString(result1) + " " + result1.length +" элементов");
System.out.println("time: " + (t11-t1) + " ms");
System.out.println("memory: " + (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory())/1000000 + " MB");
System.out.println();
Long t2 = System.currentTimeMillis();
long [] result2 = getNumbers(5);
Long t22 = System.currentTimeMillis();
System.out.println(Arrays.toString(result2));
System.out.println("time: " + (t22-t2) + " ms");
System.out.println("memory: " + (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory())/1000000 + " MB");
System.out.println();
Long t3 = System.currentTimeMillis();
long [] result3 = getNumbers(100);
Long t33 = System.currentTimeMillis();
System.out.println(Arrays.toString(result3));
System.out.println("time: " + (t33-t3) + " ms");
System.out.println("memory: " + (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory())/1000000 + " MB");
}
public static long[] getNumbers(long N) {
long[] result = null;
HashSet<Long> armstNumbers = new HashSet<>();
long[] nArr = new long[Long.toString(N).length()]; //превращаем N в массив из чисел
char[] nCharrArr = Long.toString(N).toCharArray();
for(int i=0; i<nArr.length; i++){
final int RADIX = 10;
nArr[i] = Character.forDigit((int)nCharrArr[i], RADIX);
}
Arrays.sort(nArr);
long [] proxyArr = null;
long [] proxyTenArr = null;
long [] proxyTenTenArr = null;
int maxLength = Long.toString(N).toCharArray().length;
expArr = getSumMatrix(maxLength+1);
boolean marker;
boolean proxyMarker;
boolean proxyProxyMarker;
if(N<1){
result = new long[0];
return result;
}
else if(N<10){
int zCount = 1;
while (zCount<10 && (long) zCount<N){
armstNumbers.add((long)zCount);
zCount++;
}
}else{
for(int zCount=1; zCount<10; zCount++){
armstNumbers.add((long)zCount);
}
for (int j = 2; j<maxLength; j++){
proxyArr = new long[j];
proxyTenArr = new long[j];
proxyTenTenArr = new long[j+1];
Arrays.fill(proxyArr, 1); //сперва создаем ряд чисел, где все цифры 1, потом будем увеличивать
marker = false;
while(!marker) {
proxyMarker = false;
proxyProxyMarker = false;
if (nArr.equals(proxyArr)) {
break;
}
prove(proxyArr, armstNumbers);
//System.out.println(Arrays.toString(proxyArr));
if (proxyArr[proxyArr.length - 1] == 9) {
//этот блок для прогона чисел кратных 10
proxyTenArr = proxyArr;
proxyTenArr[proxyTenArr.length - 1] = 0;
prove(proxyTenArr, armstNumbers);
//System.out.println(Arrays.toString(proxyTenArr));
proxyTenTenArr = getProxyTenTenArr(proxyTenArr);
prove(proxyTenTenArr,armstNumbers);
int proxyIndexLeft = proxyArr.length - 2;
//отвечает за "десятки" [4, 7,... proxyArr.length - 2, 7]
while (!proxyMarker) {
/*
если самое второе справа число в массиве НЕ 9 - [1, 2, 9]
увеличиваем второе справа на единицу, а самое правое число приравниваем -> [1, 3, 3]
*/
if (proxyArr[proxyIndexLeft] != 9) {
proxyArr[proxyIndexLeft]++;
proxyArr[proxyIndexLeft + 1] = proxyArr[proxyIndexLeft];
proxyMarker = true;
}
/*
если все числа левее самой правой девятки - тоже девятки -> [9, 9, 9],
значит мы перебрали все варианты и брать массив новой длины -> [1, 1, 1, 1]
*/
else if (proxyArr[proxyIndexLeft] == 9) {
long countTen = 0; //запомнить первое после ряда девяток число -> [1, 2, 9, 9]
while (proxyArr[proxyIndexLeft] == 9 && !proxyProxyMarker) {
if (proxyIndexLeft == 0 && proxyArr[proxyIndexLeft] == 9) {
marker = true;
proxyMarker = true;
proxyProxyMarker = true;
} else if (proxyIndexLeft == 0 && proxyArr[proxyIndexLeft] != 9) {
countTen = proxyArr[proxyIndexLeft];
proxyProxyMarker = true;
} else {
proxyIndexLeft--;
countTen = proxyArr[proxyIndexLeft];
}
}
while (proxyIndexLeft != proxyArr.length && !proxyProxyMarker) {
proxyArr[proxyIndexLeft] = countTen + 1;
proxyIndexLeft++;
}
proxyIndexLeft = proxyArr.length - 2;
proxyMarker = true;
}
}
} else {
proxyArr[proxyArr.length - 1]++;
}
}
}
}
ArrayList<Long> sortedList = new ArrayList(armstNumbers);
Collections.sort(sortedList);
result = new long[sortedList.size()];
for (int i=0; i<sortedList.size(); i++){
result[i] = sortedList.get(i);
}
return result;
}
public static boolean prove(long[] arr, HashSet<Long> armstNumbers){
long sum = 0;
char[] numberCharArr = new char[arr.length];
final int RADIX = 10;
for(int i=0; i<arr.length; i++){
sum += expArr[(int) arr[i]][arr.length];
numberCharArr[i] = Character.forDigit((int)arr[i], RADIX);
}
char[] sumCharArr = Long.toString(sum).toCharArray();
Arrays.sort(sumCharArr);
Arrays.sort(numberCharArr);
if(sumCharArr.length != numberCharArr.length){
return false;
}
for(int i=0; i<numberCharArr.length; i++){
if(numberCharArr[i] != sumCharArr[i]){
return false;
}
}
armstNumbers.add(sum);
return true;
}
public static long[][] getSumMatrix(int numberMax){
long[][] expArr = new long[10][];
for(int i=0; i<10; i++){
expArr[i] = new long[numberMax];
for (int j=0; j<numberMax; j++){
expArr[i][j] = (long) Math.pow(i, j);
}
}
return expArr;
}
public static long[] getProxyTenTenArr(long[] arr){
long [] tenTenArr = new long[arr.length+1];
for(int i=0; i<arr.length; i++){
tenTenArr[i] = arr[i];
}
tenTenArr[tenTenArr.length-1] = 0;
tenTenArr[tenTenArr.length-2] = 0;
return tenTenArr;
}
}
/*
Алгоритмы-числа
Число S состоит из M цифр, например, S=370 и M (количество цифр) = 3
Реализовать логику метода getNumbers, который должен среди натуральных чисел меньше N (long)
находить все числа, удовлетворяющие следующему критерию:
число S равно сумме его цифр, возведенных в M степень
getNumbers должен возвращать все такие числа в порядке возрастания.
Пример искомого числа:
370 = 3*3*3 + 7*7*7 + 0*0*0
8208 = 8*8*8*8 + 2*2*2*2 + 0*0*0*0 + 8*8*8*8
На выполнение дается 10 секунд и 50 МБ памяти.
Требования:
1. В классе Solution должен присутствовать метод getNumbers c одним параметром типа long.
2. Метод getNumbers должен быть публичным.
3. Метод getNumbers должен быть статическим.
4. Метод getNumbers должен возвращать массив чисел удовлетворяющих условию задачи.
*/