Рекурсивная функция получает три параметра, высоту площади, ее длину и двухмерный массив высот и длин прямоугольников

Тут такую задачку нам дали ... Я уже над ней дней пять бьюсь и все никак не сделаю , мысли есть но как их на бумагу (всмысле в программу) сосредоточить не знаю , ну ладно ближе к делу ....
Есть двухмерный массив размеров прямоугольников (a[i][j] , где i это высота прямоугольника , и j его длина, также дана некая площадь x*y. Рекурсивная функция получает три параметра , высоту площади , ее длину и двухмерный массив высот и длин прямоугольников , возвращает двухмерный массив размера заданной территории , где каждая ячейка это индекс прямоугольника который был вставлен.
Чтоб понятней было я пример приведу ...

К примеру массив длин и высот выглядит таким образом

121111
312221

и территория 3х4

тогда рекурсивная функция должна вернуть следующее

0001
2251
3344

Как это сделать впринципе понятно , но возникает проблема , поскольку надо перебрать все варианты , а изменять структуру функции нельзя. Буду признателен за любые советы

0

> но возникает проблема , поскольку надо
> перебрать все варианты

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

> а изменять структуру функции нельзя

А что, нельзя из этой функции f1 с жестко заданной сигнатурой вызвать свою собственную функцию f2, которая имеет те параметры, какие тебе хочется, и уже f2 вызывать рекурсивно?

Отчего же , можно создать любое количество вспомогательных функций.
Теперь про дерево решений , насколько я понял это когда изначально все индексы прямоугольников выстраиваются в цепочку и потом от каждого индекса идет еще одна цепочка и так далее тоесть :

Например (индексы в массиве прямоугольников)

0 1 2 3 4 5
1 2 3 4 5 0 2 3 4 5 0 1 3 4 5 0 1 2 4 5 0 1 2 3 5 0 1 2 3 4

и т.д. Но тогда возникает вопрос как без использования глобального массива (размером заданной территории) , программа будет пытаться туда вставить прямоугольник под индексом n , ведь может быть такой случай что оставшая площадь не может быть выражена как x*y

например

0 0 0 1 (x - свободное место в площади 3*4)
x x x 1 Как выразить остаток площади в данном случае ???
x x x x

Буду признателен , если подкините идею , или вкратце напишете как это можно обойти...
Заранее спасибо.

0

Поступаю ужасно непедагогично и посылаю решенную на 60% задачу

В общем, мне представляется вот такое решение. Можно было бы обойтись без рекурсии, но уж если в условии фигурировала рекурсивная функция, то... Собственно, под поиском по дереву решений я имел в виду то, что делает функция mainRecursiveFunction(). Привести исходные данные к нужному виду и дописать внутренности всех методов - дело техники.

Сергей большое спасибо за ответ , я тут что-то похожое успел накатать и могу сказать что получилось почти как у вас ну только с некоторыми изменениями , если интересно то вот что получилось ...

class Frame {

static int [][] _frame;

private static void Update(int what,int with)
{
for (int a=0;a<_frame.length;a++)
for (int b=0;b<_frame[a].length;b++)
if (_frame[a][b] == what) _frame[a][b]=with;
}

private static int Insert(int height,int width,int index) // Function that tries to insert
{ // a rectangle with specified height & width
int x=0,y=0,a=height,b=width; // it gets [x][y] of rectangle and its number in the main array
// on exit it returns : 1 if succeded and 0 if failed.

for (x=0;x<_frame.length;x++)
{
for (y=0;y<_frame[0].length;y++)
{
if (_frame[x][y] == -1)
break;
}
if (y != _frame[0].length && _frame[x][y] == -1) break;
}

int Y_index=y,X_index=x;
for (x=X_index;a>0 && x<_frame.length;x++)
{
for (y=Y_index,b=width;b>0 && y<_frame[x].length;y++)
if (_frame[x][y] == -1)
{
b--;
_frame[x][y]=-2;
}
if (b == 0) a--;
else
{
Update(-2,-1);
return 0;
}
}

if (a!=0 || b!=0)
{
Update(-2,-1);
return(0);
}

Update(-2,index);
return (1);
}

private static int [][] Mirror(int [][] rectangles, int [][] buffer)
{
for (int a=0;a<rectangles.length;a++)
for (int b=0;b<rectangles[a].length;b++)
buffer[a][b]=rectangles[a][b];
return(buffer);
}

private static int GetRectLeft(int [][]rectangles)
{
int count=0;
for (int a=0;a<rectangles[0].length;a++)
if (rectangles[0][a] !=0) count++;
return(count);
}

private static int GetFreeSpace()
{
int count=0;
for (int a=0;a<_frame.length;a++)
for (int b=0;b<_frame[a].length;b++)
if(_frame[a][b] == -1) count++;
return (count);
}

public static int[][] fillFrame( int height, int width, int[][] rectangles ) {
int count=0,current=-1,b=0;
int [][] frame = _frame;
int [][] buffer = new int [rectangles.length][rectangles[0].length];
Mirror(rectangles,buffer);
if (GetFreeSpace() == 0) return (_frame);
for (b=GetRectLeft(rectangles),count=0;count <rectangles[0].length && b>0;count++)
{
if (rectangles[0][count] !=0)
{
if (Insert(buffer[0][count],buffer[1][count],count) ==0)
b--;
else
{
current=count;
buffer[0][count]=0;
buffer[1][count]=0;
frame=fillFrame(height,width,buffer);
if (frame != null) return(frame);
Update(current,-1);
buffer[0][current]=rectangles[0][current];
buffer[1][current]=rectangles[1][current];
}
}
}
return(null);
}


public static void sortRectangles( int[][] rectangles ) {
int [] temp = new int [2];

for (int count1=0;count1<rectangles[0].length;count1++)
{
for (int count2=count1;count2<rectangles[0].length;count2++)
{
if ((count2+1 < rectangles[0].length) && (rectangles[0][count1]*rectangles[1][count1] < rectangles[0][count2+1]*rectangles[1][count2+1]))
{
temp[0]=rectangles[0][count1];
temp[1]=rectangles[1][count1];
rectangles[0][count1]=rectangles[0][count2+1];
rectang

0