Help fix the program code, which in theory should solve the following problem:

Actually the task itself: A room with the size of n * m units is required to be covered with identical parquet tiles of the size of 2 * 1 units without gaps and overlays (m <= 20, n <= 8, m, n are integer). The floor can be covered with parquet in various ways. It is required to determine the number of all possible ways of laying parquet for specific values ​​of m <= 20, n <= 8. The result of the task is a table containing 20 rows and 8 columns. The element of the table is a number, which is the solution of the problem for the corresponding n and m.

Links to the explanation of the solution: Okulov. Programming in Algorithms p. 120

And the code:

import java.math.BigInteger; public class Main { //Временная, для вычислений static BigInteger[][] B = new BigInteger[256][21]; //Результирующая таблица static BigInteger[][] A = new BigInteger[9][21]; //Вычисляет k - ю степень 2 public static long St2(int k) { if (k <= 0) { return 1; } else { return (long) Math.pow(2, k); } } //{k,l -номера сечений, pi - количество анализируемых разрядов сечений} public static boolean Can(int k, int l, int pi) { int i; long d; boolean b, res; res = false; b = false; for (i = 1; i <= pi; i++) { d = St2(i); if ((k & d) == 0){ //{определяется значение разряда с номером d для сечения k} if ((l & d) == 0) {//если d-тый разряд 1-го сечения - 0, сравнивается d-тый разряд 2-го сечения b = !b; /**если d-тый разряд первого и второго сечения = 0, значение b меняется на противоположное, затем *чтобы при нечетном количестве нулей выбивало из метода с результатом false */ } else { // kd = 0, ld = 1 if (b) { // если b = true return false; // завершение метода - false, срабатывает в случаях когда количество 0 перед 1 нечетно /** * Метод завершается с результатом false в случаях * d = 00 || l = 10 - корректно * d = 0000 || l = 1000 - корректно * */ } } } else if (((l & d) != 0) || b) { return false; } } ; res = !b; return res; } //Основная логика public static void Solve() { int i, j, k, l; long max; //Цикл по значению длины комнаты for (i = 1; i <= 8; i++) { max = St2(i) - 1; B[0][0] = BigInteger.ONE; //Цикл по значению ширины комнаты for (j = 1; j <= 20; j++) { //цикл для обсепечения всей ширины комнаты сечениями //Сечение с номером k for (k = 0; k <= max; k++) { //Сечение с номером l for (l = 0; l <= max; l++) //if (Can(k,l,i)) { //Проверка совместимости сечений boolean r = Can(k, l, i); if (r) { B[k][j] = B[k][j].add(B[l][j - 1]); } } } A[i][j] = B[0][j]; } } } public static void main(String[] args) { //забиваем нулями таблицы for (int m = 0; m <= 20; m++) { for (int n = 0; n <= 8; n++) { A[n][m] = BigInteger.ZERO; } } for (int m = 0; m <= 20; m++) { for (int n = 0; n <= 255; n++) { B[n][m] = BigInteger.ZERO; } } //производим расчет Solve(); //выводим результаты for (int m = 1; m <= 20; m++) { for (int n = 1; n <= 8; n++) { if (n * m % 2 != 0) { String val="*"; for(int p=0;p<25;p++) val+=" "; System.out.print(val); } else if (m == 1 && n % 2 == 0) { String val="1"; for(int p=0;p<25;p++) val+=" "; System.out.print(val); } else { String val=A[n][m].toString(); int v=val.length(); for(int p=0;p<26-v;p++) val+=" "; System.out.print(val); } } System.out.println(); } } }

It does not work correctly because: if m or n = 2, the number of ways of laying tiles is a Fibonacci sequence, the program gives something else. + Can method (0, 3, 4) i.e. for sections 0 and 3 and with a floor length of 4 (the number of bits of int-sections in binary representation) returns false, although obviously it should be true

    2 answers 2

    You have a serious logic error:

      for (i = 1; i <= 8; i++) { max = St2(i) - 1; .... Can(... i);

    Here you are doing a cycle on the width of the room (let's agree, what is less than 8, then the width). At the same time, this cycle is not needed at all for the calculation at a specific width. If you want to get answers for different widths, then it should be done in a different array. Quick edit - fix i = N. You don’t need long arithmetic here, the maximum answer (for 8 * 20) is 3547073578562247994 which is quite long . But it makes reading difficult. Then you need to number the bits from 1 ( can method):

      for (i = 1; i <= pi; i++) { d = St2(i);

    What gives the wrong answer.

    By the way, where do you check that the masks do not overlap? if (((l & d) != 0) || b) there is no need to check b ..

    Degree 2 calculate through Math.pow cuts the eyes, there is the same bit shift.

    In general, you can sit here with a debugger for a long time. Here is my solution written on my knee.

     long long Res[21][256]; char goodMask[256]; int pow2[8]; int N = 8,M = 20; bool good(int mask){ int pos = N-1; while (pos >= 0) if ( ~mask& pow2[pos] ) if (!pos) return 0; else if (mask& pow2[pos - 1]) return 0; else pos-=2; else pos--; return 1; } int main() { for (int i=0;i<N;i++) pow2[i] = 1<<i; int border = (1 << N); for (int i=0;i<border;i++) goodMask[i] = good(i); Res[0][0] = 1; for (int pos = 0; pos <M; pos++) for (int i=0;i<border;i++) //Left Mask for (int j=0;j<border;j++)//Right Mask if ( !(i&j)) //no intersect if (goodMask[i|j]) Res[pos+1][j]+=Res[pos][i]; for (int i=0;i<=M;i++) cout << Res[i][0]<<" "; return 0; }

    I think having this to add your decision will be easy.

    • "it will be easy" - not familiar with C ++. I'll try to figure out nothing to do. About "number bits 1" and Math.pow agree. - Serg4356
    • if (((l & d)! = 0) || b) - here is a check for the absence of such 101 constructions - Serg4356
    • @ Serg4356 if they intersect, then check for b is not necessary. Already can not. - pavel
    • can you explain? but I do not keep up - Serg4356
    • @ Serg4356 I have a question first) and what does your unit in the mask mean, can you formulate? - pavel

    Left attempts to modify someone else's code, instead of mine:

     import java.util.ArrayList; public class Parquet{ // метод для сопоставления сечений public static boolean acceptCut(int firstCut, int secondCut, int digitsCount){ int countSecond = 0;// переменная для хранения кол-ва 0 во втором сечении for(int i=0;i<digitsCount;i++){//цикл по каждому разряду сечения int digit = (1<<i);// маска if((firstCut&digit)==0) {//если i-ый разряд 1-го сечения =0 if ((secondCut & digit) == 0) {//если i-ый разряд 2-го сечения =0 countSecond++; } else {//если i-ый разряд 2-го сечения !=0 if(countSecond%2!=0) return false;// и кол-во 0 во втором сечении - нечетно } } else {//если i-ый разряд 1-го сечения !=0 if ((secondCut & digit)!=0) return false; // (countSecond%2!=0)|| и кол-во 0 во втором сечении - нечетно } } if((countSecond%2!=0)) return false;//(countFirst%2!=0)|| return true; } //метод для нахождения решений для заданных mn public static String countValues(int digitsCount, int roomWidth){ ArrayList resArray = new ArrayList(); ArrayList resArray2 = new ArrayList(); String res ="0", res2=""; long resNumber = 0; int maxi = 1<<digitsCount; int maxy= 1<<digitsCount; if(digitsCount*roomWidth%2!=0) return "*"; //устанавливаем первоначальные значания для resArray resArray.add(0); //используем значения из resArray перебираем подходящие outer: for(int i=0; i<roomWidth;i++) { for (int x = 0; x < maxy; x++) {//resArray.size() res.length() тут использую лист для сохранения подходящих значений, так по крайней мере работает if (i == (roomWidth - 1)) maxi = 1; for (int z = 0; z < maxi; z++) { if (acceptCut(x, z, digitsCount)) {//(Integer) resArray.get(x) |||| acceptCut(Integer.parseInt(Character.toString(res.charAt(x))) System.out.println(x + "|" + fullString(x, digitsCount) + "|" + z + "|" + fullString(z, digitsCount) ); /** resArray2.add(z); res2 += z; */ if (i == (roomWidth - 1)) { resNumber++; } } } if(i==0) continue outer; } /** resArray.clear(); for (int x = 0; x < resArray2.size(); x++) { resArray.add(resArray2.get(x)); } resArray2.clear(); res = res2; res2 = ""; */ } return Long.toString(resNumber); } public static void main(String[] args) { // System.out.println(fullString(3,4)); /** for(int i = 1; i<=20; i++) { System.out.println(countValues(i, 2) + "|" + countValues(2, i) + "|"); } */ // System.out.println(countValues(3,2)); System.out.println(acceptCut(2,0,3)); System.out.println(acceptCut(0,2,3)); } }

    What are the disadvantages: using ArrayList is clearly not the best solution. When trying to use the maximum values ​​(8,20) error: Java heap space. Why I chose this way - to save the values ​​of the right (if we compare left to right) sections and then substitute the left ones. I do not understand whether you can set an algorithm for finding them. For example:

    enter image description here

    In my acceptCut () method there is a check for an odd consecutive number of pairs of zeros. So, the 3rd section (in the figure) just does not fit the logic, i.e. it can be generated in the search in any place, but in fact it can occur only after the 2nd section - so I thought it was the right decision to save. In general, it seems like it works if you use Arraylist, but this is not accurate (checked for length / width 2 - the Fibonacci sequence is obtained). But if the logic and brute force, then there are such situations acceptCut (2,0,3) = true, a acceptCut (0,2,3) = false

    • @pavel can see? - Serg4356