C: алгоритм разрезания прямоугольника на квадраты

Question

Я попытался выполнить эту задачу из Codewars и пропустил свой код через компилятор.Это указывало на ошибку сегментации, но я не знаю, где я иду не так.Задача состоит в следующем:

Рисунок ниже дает представление о том, как разрезать данный «истинный» прямоугольник на квадраты («истинный» прямоугольник, означающий, что два измерения различны).

Можете ли вы перевести этот рисунок в алгоритм?

Вам будет дано два измерения - положительная целая длина (параметр с именем lng) и положительная целая ширина (параметр с именем wdth),Вы вернете массив.

Мой код выглядит следующим образом:

typedef struct Data Data;
struct Data {
     int *array;
     int sz;
};

Data* sqInRect(int lng, int wdth) {
  Data* ptr = (Data*) malloc(sizeof(Data));
  // if square length == square width
  if(lng == wdth){
    ptr->array = NULL;
    ptr->sz = 0;
    return 1;
  }
  //initialise variables
  int rmdLength,rmdWidth,rmdSmallSquares,rmdLengthTimes,rmdWidthTimes,SIZE,temp=0;

  //assign length to temporary rmd variable
  rmdLength = lng;
  //calc how many squares of side *wdth* inside rect
  while((lng-wdth)>wdth){
    rmdLength -= wdth;
    rmdLengthTimes++;
  }
  rmdLength -= wdth;
  rmdLengthTimes++;
  //assign width to temporary rmdWidth variable
  rmdWidth = wdth;
  //calc how many squares of side *rmdWidth* inside rect (remaining area)
  while(rmdWidth>rmdLength){
    rmdWidth -= rmdLength;
    rmdWidthTimes++;
  }
  rmdWidth -= rmdLength;
  rmdWidthTimes++;
  //calculate final number of remaining squares
  rmdSmallSquares = rmdLength/rmdWidth;
  //calculate SIZE
  SIZE = rmdLengthTimes + rmdWidthTimes + rmdSmallSquares;
  //declaration of array
  int arr[SIZE];
  //for loop to put square values in array
  temp = rmdLengthTimes + rmdWidthTimes;
  for(int i=0;i<rmdLengthTimes;i++){
    arr[i] = wdth;
  }
  for(int j=rmdLengthTimes;j<temp;j++){
    arr[j] = rmdLength;
  }
  for(int k=temp;k<SIZE;k++){
    arr[k]= rmdWidth;
  }
  //get Data* ptr to store array AND size of that array
  ptr->array = arr;
  ptr->sz = SIZE;
  return ptr;
}

Буду признателен, если кто-нибудь сможет уточнить со мной, где я ошибся.Я застрял на этой проблеме слишком долго.Спасибо.

Answer 1

У вас много переменных, неинициализированных в следующей строке:

  int rmdLength,rmdWidth,rmdSmallSquares,rmdLengthTimes,rmdWidthTimes,SIZE,temp=0;

Примечание: В приведенной выше строке не будет инициализировать все переменные 0.Он только инициализирует temp 0.

Чтобы инициализировать все переменные 0, вы должны сначала объявить их, а затем инициализировать их следующим образом:

int rmdLength, rmdWidth, rmdSmallSquares, rmdLengthTimes, rmdWidthTimes, SIZE, temp;  
rmdLength = rmdWidth = rmdSmallSquares = rmdLengthTimes = rmdWidthTimes = SIZE = temp = 0;

использование неинициализированных переменных приводит к неопределенному поведению:
из онлайн-ссылки cpp на неинициализированные переменные :

Значение в неинициализированной переменной может быть любым - оно непредсказуемо,и может отличаться при каждом запуске программы. Чтение значения неинициализированной переменной - неопределенное поведение - что всегда плохая идея.Он должен быть инициализирован значением, прежде чем вы сможете его использовать.

Кроме того, в следующем коде вы используете неинициализированную переменную rmdLengthTimes в качестве проверки для перебора массива:

 for(int i=0;i<rmdLengthTimes;i++){
    arr[i] = wdth;
  }

Это приведет к доступу к outадрес памяти, который также является неопределенным поведением:

с wiki :

Поведение некоторых языков программирования - наиболее известный Cи C ++ - в некоторых случаях не определено .В стандартах для этих языков семантика определенных операций описана как неопределенная.Эти случаи обычно представляют однозначные ошибки в коде, например, , например, индексирование массива за пределами его границ .

Так что правильная инициализация всех переменных перед их использованием решит вашу проблему.

Answer 2

Вы обращаетесь за пределы массива arr.

arr[i] = wdth;

Поскольку вы не инициализировали указанные ниже переменные;

  int rmdLength,rmdWidth,rmdSmallSquares,rmdLengthTimes,rmdWidthTimes,SIZE,temp=0;

И используете их как index для массиваприведет к неопределенному поведению.

  SIZE = rmdLengthTimes + rmdWidthTimes + rmdSmallSquares;

  for(int k=temp;k<SIZE;k++){
    arr[k]= rmdWidth;
  }

Инициализируйте, как показано ниже.

  int rmdLength=0,rmdWidth=0,rmdSmallSquares=0,rmdLengthTimes=0,rmdWidthTimes=0,SIZE=0,temp=0;