Форум Flasher.ru - Задачка

Форум Flasher.ru (http://www.flasher.ru/forum/index.php)

- Флейм (http://www.flasher.ru/forum/forumdisplay.php?f=53)

- - Задачка (http://www.flasher.ru/forum/showthread.php?t=181615)

Предлагаю, на мой взгляд, интересную задачку. Не обязательно решать на AS, хоть на чем. Поэтому и в общем.

Задача заключается в следующем:
- нужно разбить содержание массива / списка / стека и т.п. на колонки. При чем, в исходной коллекции элементы упорядочены по какому угодно принципу. Для наглядности я буду использовать цифры, но это может быть что угодно.
Разбить нужно таким образом, чтобы максимально заполнить все колонки. Колонки нужно заполнять вертикально последовательно элементами из коллекции. Например:

[1, 2, 3, 4, 5, 6, 7]

разбив на 5 колонок получим:

|1| |3| |5| |6| |7|
|2| |4|

Естественно, количество элементов и колонок могут быть произвольными.

Да, еще, конечно, важное условие: колонки должны быть максимально уравновешены, т.е. вариант когда все элементы - (количество колонок - 1) складываются в первую колонку, а оставшиеся - во все остальные не проходит.

что-то мне тут Беллман мерещится, но сходу так не соображу. На буратину с яблоками чем-то похоже.

Интересно. А мне что-то из расчетов поверхностного натяжения:)

а вот взять по-простому и рассовать, не ?

Код AS3:

var i:int, j:int, k:int;

var data:Array = [1, 2, 3, 4, 5, 6, 7];

var res:Array = [];

 

var w:int = 5;

var len:int = data.length;

var h:int = Math.ceil(len / w);

 

for (i = 0; i < h; i++) res[i] = [];

 

k = 0;

for (j = 0; j < w; j++) 

{

 

        for (i = 0; i < h ; i++) 

        {

 

                res[i][j] = data[k++];

                if (--len < w - j) break;

        }

}

 

for (i = 0; i < h; i++) trace(res[i]);

Есть один неприятный момент, который разрушает чувство прекрасного в этом коде :) когда количество элементов делится нацело на количество колонок - 1, получается что в предпоследней колонке на один элемент меньше чем у остальных, а в последней всего один элемент. Например, когда data = [1, 2, 3, 4, 5, 6, 7, 8, 9], w = 4. В таком случае хотелось бы одну колонку делать выше остальных, а не вразнобой :)

Цитата:

В таком случае хотелось бы одну колонку делать выше остальных, а не вразнобой

Пример?:)

Что-то сложность не понятна: вот как silin сделал, в чем подвох?

Артём, там подвох в том, что колонки набираются последовательно и при некоторых случаях последняя колонка будет с одним элементом, в то время, как все остальные с 4-мя, например. Нужно, чтобы все колонки набирались равномерно ровно до тех пор, пока не останутся последние элементы.

Проще проиллюстрировать:

Код:

1,4,7,9

2,5,8

3,6

Код:

1,4,6,8

2,5,7,9

3

Больше часа пробую такое запрогать, сложновато и заманчиво :)

Добавлено через 1 час 23 минуты
У меня пока что так получилось (наверняка с ошибками):

Код AS3:

var data:Array = [1,2,3,4,5,6,7,8,9];

var w:int = 4;

var res:Array = [];

var rows:int = Math.ceil(data.length / w);

var endCount:int = data.length % w;

var i:int = 0;

var j:int = 0;

var k:int = 0;

var pos:int = 0;

 

for (i = 0; i < rows + 10; i++) {

        res[i] = [];

}

for (k = 0; k < data.length; k ++) {

        pos = k % rows;

        if (pos == rows - 1) {

                j++;

        }

        if (j > endCount && endCount != 0) {

                pos = k % (rows - 1); // Вот тут косяк :(

        }

        res[pos].push(data[k]);

}

for (i = 0; i < rows; i++) {

        trace(res[i]);

}

Код AS3:

package

{

        import flash.display.Sprite;

 

        public class PrintColumns extends Sprite

        {

                /**

                 * http://stackoverflow.com/questions/1...-into-x-colums

                 */

                public function PrintColumns()

                {

                        super();

                        trace(printColumns([1, 2, 3, 4, 5, 6, 7, 8, 9], 4));

                }

 

                private function printArray(source:Array):String

                {

                        return source.join(" ") + "\n";

                }

 

                private function printColumns(source:Array, numColumns:int):String

                {

                        var output:String = "";

                        var columns:Array = new Array(numColumns);

                        var printPositions:Array = new Array(numColumns);

                        var printed:Array;

                        var i:int;

                        var columnLength:int = Math.ceil(source.length / numColumns);

                        var printedAlready:int;

                        var nextBunch:int;

 

                        printPositions[0] = 0;

                        while (i < numColumns)

                        {

                                if (source.length - (printedAlready + columnLength) < numColumns - i)

                                        nextBunch = columnLength - 1;

                                else nextBunch = columnLength;

                                printPositions[i + 1] = printedAlready + nextBunch;

                                columns[i] = printPositions[i + 1] - printPositions[i];

                                printedAlready += nextBunch;

                                i++;

                        }

                        i = 0;

                        printed = new Array(numColumns);

                        while (i < columnLength)

                        {

                                for (var j:int = 0; j < numColumns; j++)

                                {

                                        if (columns[j])

                                        {

                                                printed[j] = source[printPositions[j]];

                                                printPositions[j]++;

                                                columns[j]--;

                                        }

                                        else printed[j] = " ";

                                }

                                output += printArray(printed);

                                i++;

                        }

                        return output;

                }

        }

}

По поводу примера, ну вот, собственно, смысл тот же, что и у silin'a и работает так же. В распечатке получаем:

Код:

а хотелось бы:

Код:

т.е. чтобы только одна колонка максимум, отличалась по высоте от других.

ПС. Алгоритм такой потому что это адаптация со списков, и не хотелось во время распечаток много памяти ис пользовать. Но разница не существенная.

Код AS3:

                private function init(e:Event = null):void {

                        removeEventListener(Event.ADDED_TO_STAGE, init);

                        var txt:TextField=new TextField();

                        txt.autoSize = TextFieldAutoSize.LEFT;

                        txt.multiline=true;

 

                        var input:Array = [1,2,3,4,5,6,7,8,9];

                        const lines:int = 4;

 

                        var length:int = input.length;

                        var itemsInLine:int = length / lines;

                        var outfit:int = length - itemsInLine * lines;

                        var result:Array = [];

                        var c:int = 0;

                        var m:int = 0;

                        while (c < length){

                                result[m] = [];

                                for (var i:int = 0; i < itemsInLine; i++) result[m].push(input[c++]);

                                if (outfit-- > 0) result[m].push(input[c++]);

                                m++;

                        }

 

                        for (var k:int = 0; k<result.length; k++){

                                txt.appendText(result[k]+"\n")

                        }

                        addChild(txt);

                }