Искусство программирования - 8

[LazarusLong]

Есть массив размерностью MxN (могут быть как равны, так и не равны).

Необходимо заполнить массив числами от 1 до MxN по спирали, то есть к примеру для M = 3, N = 4 массив будет иметь вид:

1	2	3	4
10	11	12	5
9	8	7	6

Принимаются ответы на языках С/С++, Паскаль, Java, C#. Автору самого короткого решения - +1, так же автору наиболее оргинального решения(по моему усмотрению) - +1.

Задача, на самом деле, довольно тривиальна, но хочется поднять темы по программированию, а то отгадывание рож уже поднадоело.

[LazarusLong]

Вариантов не будет? Можно оглашать ответ?

ЗЫ:Неужели так сложно?

[Alder]

LazarusLong, подожди. Я вечерком подумаю

[Polyakov]

Если мне не изменяет память, то эта задача была в билетах рейтинга по информатике для поступающих в ВУЗ на специальность ИУС и КСД в 2002 году. Уровень этой задачи 6 балов из 60 возможных при выделении на все задачи 3 часов времени.
Тема вроде бы называется "Искусство программирования" - так причем здесь задача школьного уровня?

[EvilMax]

Задачка простая. Усложнение в том, чтобы написать как можно более компактный и эффективный код. Если не будут гуглить, то смысл есть.

[LazarusLong]

так причем здесь задача школьного уровня?

Как я написал - задача тривиальная. Просто давно не было задач по программированию и мне хотелось поднять интерес к таким викторинам. Пускай и такой вот простой задачей. Я в свое время её решил минут за 10 (когда мне её показали я был на 5-м курсе). Честно говоря ожидал ответа на эту викторину в первый час после публикации. Но, видимо, народу действтительно угадывание картинок более интересно, чем программирование. Увы.

А "Искусство программирования № N" - это просто сложившееся исторически на данном форуме заглавие для задач по программированию.

[Polyakov]

Эффективность программы обычно заключается в ее быстродействии, а минимизация кода - это величина обычно обратная быстродействию. Поэтому эффективность и компактность в программировании - это противоположные критерии, хотя не всегда угол их противоречий равен 180 градусам.
Раньше (когда была проблема с нехваткой оперативной памяти - 640К, 1, 2 или 4 М) на объем exe-модуля существенное влияние оказывала величина исходного кода и общепринято было его сокращать. Я даже помню как я был безмерно доволен собой когда для программы общим объемом где-то в 50-40 тыс.строк после очередной оптимизации кода удалось сократить exe-модуль с 400 до 320 Кбайт, что позволило для ПК на i486 с 8М оперативки увеличить производительность расчетов практически в 3-5 раз, то есть на определенные расчеты вместо 15-20 минут стало тратится 3-4 минуты.
P.S. В данном случае быстродействие достигалось за счет освобождения оперативной памяти и уменьшения операций свопирования.

[LazarusLong]

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

В общем-то все правильно, единственное что печально что как на компактность так и на быстродействие программ, в последнее время все чаще плюют с пятого этажа. Потому как в связи с удешевлением железа и общим ростом производительности компьютеров вдруг выяснилось что самым дорогим ресурсом стало время, затрачиваемое на разработку. К примеру, одна контора написала тормозящее г...., зато первой и успела продать. А другая писала аналогичную программу, вылизала её до состояния полного шика, но продать её уже не может, так как все используют то самое г.... а инерция пользовательского мышления это такая вещь, которую перебороть крайне сложно.

[EvilMax]

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

[zer_owlet]

мужики, хорош спамить! давайте код, а не ваши расмазывания мысли по стеклу! это не ученый совет, тут правктику показать надо )))

ЗЫ: я в этой задаче пролетаю по фильтру языков...

[Alder]

zer_owlet, напиши на php. Я думаю, что поймем код.

[LazarusLong]

Специально для него сделаю исключение и приму код на пхп )))

[Alexandr]

Если не будут гуглить, то смысл есть.

вот она подсказка к решению))

[artri]

Рискну предложить свое решение 

Код:

package test;

public class test1App {
    
    private static final int M = 3;
    private static final int N = 4;
    private enum Direction{left, right, top, bottom}

    private int rows;
    private int cols;
    private Integer[][] matrix;

    public test1App() {
        this(M,N);
    }

    public test1App(int rows, int cols) {
        if((rows <2) || (cols <2)){
            throw new RuntimeException("Failed to create required matrix!");
        }
        this.rows = rows;
        this.cols = cols;
        this.matrix = fillMatrix();
    }

    private Integer[][] initMatrix(){
        Integer matrix[][] = new Integer[this.rows][this.cols];
        for(int i1=0; i1<this.rows; i1++){
            for(int i2=0; i2<this.cols; i2++){
                matrix[i1][i2] = 0;
            }
        }
        return matrix;
    }

    private void printMatrix(){
        for(int i1=0; i1< this.rows; i1++){
            for(int i2=0; i2<this.cols; i2++){
                System.out.print(Integer.toString(matrix[i1][i2])+" ");
            }
            System.out.println();
        }
    }

    private Integer[][] fillMatrix(){
        Integer[][] matrix = initMatrix();
        int x = 0, y = 0;
        Direction direction = Direction.right;
        int xlowlim = 0, xhighlim = cols-1;
        int ylowlim = 1, yhighlim = rows-1;
        for(int value = 1; value <= cols*rows; value++){
            matrix[y][x] = value;

            switch(direction){
                case right:{
                    x++;
                    if(x == xhighlim){
                        xhighlim--;
                        direction = Direction.bottom;
                    }
                    break;}
                case bottom: {
                    y++;
                    if(y == yhighlim){
                        yhighlim--;
                        direction = Direction.left;
                    }
                    break;}
                case left:{
                    x--;
                    if(x == xlowlim){
                        xlowlim++;
                        direction = Direction.top;
                    }
                    break;}
                case top:{
                    y--;
                    if(y == ylowlim){
                        ylowlim++;
                        direction = Direction.right;
                    }
                    break;}

            }
            
        }
        return matrix;
    }

    public void run(){
        printMatrix();
    }

    public static void main(String[] args){
        try{
            test1App test1 = new test1App(6,2);
            test1.run();
        }catch(Throwable ex){
            ex.printStackTrace();
        }
    }
}

З.Ы.

Задачка простая. Усложнение в том, чтобы написать как можно более компактный и эффективный код. Если не будут гуглить, то смысл есть.

Не гуглил...

[pfa]

Рискну предложить свое решение  Улыбка

Ужос...

[Storm]

Решение классика классикой ни компактное, ни красивое, ИМХО.... Но коль других уж нет...
Писал на Perl, на С будет аналогично, разве что вместо elsif придется  флаг вешать.

Выводит на экран:

Код:

$ ./iskus_prog8.pl
0 0 0
0 0 0
0 0 0
0 0 0
1 10 9
2 11 8
3 12 7
4 5 6

Исходник:

Код: (perl)

#!/usr/bin/perl -w

use strict;

use constant N => 4;
use constant M => 3;

sub printmat;

my @a;
my ($i,$j);

for($i=0;$i<N;$i++)
{
  for($j=0;$j<M;$j++)
    {
	  $a[$i][$j]=0;
	}

}

printmat;

my $cnt=1;
my $flag=0;
$i=0;
$j=0;
my $dirx=1;
my $diry=0;


while($cnt<=N*M){

  if(($i<N)&&($j<M)&&($a[$i][$j]==0)){
    $a[$i][$j]=$cnt;
    $cnt++;
	$i+=$dirx;
	$j+=$diry;
  }else{
	$i-=$dirx;
	$j-=$diry;
   if($dirx==1 && $diry==0)
   { 
     $dirx=0;
	 $diry=1;   
   
   }elsif($dirx==0 && $diry==1)
     {
	   $dirx=-1;
	   $diry=0;   
	 }elsif($dirx==-1 && $diry==0)
     {
	   $dirx=0;
	   $diry=-1;   
	 }elsif($dirx==0 && $diry==-1)
     {
	   $dirx=1;
	   $diry=0;   
	 }
	$i+=$dirx;
	$j+=$diry;
  }
  
  
} 

printmat;

sub printmat
{
  my $i;
  my $j;
  
  for($i=0;$i<N;$i++)
  {
  for($j=0;$j<M;$j++)
    {
	  print $a[$i][$j]," ";
	}
	print "\n";
  }
}

Развернуть направления заполнения для данного алгоритма легко и просто, главное по спирали.
Зануление на Perl делать не обязательно было, но для алгоритма в целом этот момент важен.

[artri]

пошли алгоритмы, а то сплошной флейм и оффтоп