КИТА unofficial

Ваши интересы => Викторины и конкурсы => Тема начата: LazarusLong от Октябрь 18, 2008, 12:50:05



Название: Искусство программирования - 8
Отправлено: LazarusLong от Октябрь 18, 2008, 12:50:05
Есть массив размерностью MxN (могут быть как равны, так и не равны).

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

1234
1011125
9876

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

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


Название: Re: Искусство программирования - 8
Отправлено: LazarusLong от Октябрь 23, 2008, 06:38:23
Вариантов не будет? Можно оглашать ответ?

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


Название: Re: Искусство программирования - 8
Отправлено: Alder от Октябрь 23, 2008, 06:41:47
LazarusLong, подожди. Я вечерком подумаю :)


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


Название: Re: Искусство программирования - 8
Отправлено: EvilMax от Октябрь 23, 2008, 10:56:20
Задачка простая. Усложнение в том, чтобы написать как можно более компактный и эффективный код. Если не будут гуглить, то смысл есть.


Название: Re: Искусство программирования - 8
Отправлено: LazarusLong от Октябрь 23, 2008, 11:17:30
так причем здесь задача школьного уровня?
Как я написал - задача тривиальная. Просто давно не было задач по программированию и мне хотелось поднять интерес к таким викторинам. Пускай и такой вот простой задачей. Я в свое время её решил минут за 10 (когда мне её показали я был на 5-м курсе). Честно говоря ожидал ответа на эту викторину в первый час после публикации. Но, видимо, народу действтительно угадывание картинок более интересно, чем программирование. Увы.

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


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


Название: Re: Искусство программирования - 8
Отправлено: LazarusLong от Октябрь 23, 2008, 11:40:17
Эффективность программы обычно заключается в ее быстродействии, а минимизация кода - это величина обычно обратная быстродействию. Поэтому эффективность и компактность в программировании - это противоположные критерии, хотя не всегда угол их противоречий равен 180 градусам.
В общем-то все правильно, единственное что печально что как на компактность так и на быстродействие программ, в последнее время все чаще плюют с пятого этажа. Потому как в связи с удешевлением железа и общим ростом производительности компьютеров вдруг выяснилось что самым дорогим ресурсом стало время, затрачиваемое на разработку. К примеру, одна контора написала тормозящее г...., зато первой и успела продать. А другая писала аналогичную программу, вылизала её до состояния полного шика, но продать её уже не может, так как все используют то самое г.... а инерция пользовательского мышления это такая вещь, которую перебороть крайне сложно.


Название: Re: Искусство программирования - 8
Отправлено: EvilMax от Октябрь 23, 2008, 11:46:38
Да, как правило, оптимизация по быстродействию часто противоположна оптимизации по размеру. Но быстродействие зависит и от скорости загрузки, т.е. от размера исполняемого кода и объёма данных. Так что компромисс иногда надо искать. А минимизация кода за счёт более профессионально составленного алгоритма, скорее всего, приведёт и к росту быстродействия. Для небольших алгоритмов можно и мозгами покрутить, как их оптимизировать и по размеру и по скорости.
Ну а маркетинг... речь не о нём в этой теме.


Название: Re: Искусство программирования - 8
Отправлено: zer_owlet от Октябрь 24, 2008, 10:54:08
мужики, хорош спамить! давайте код, а не ваши расмазывания мысли по стеклу! это не ученый совет, тут правктику показать надо )))

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


Название: Re: Искусство программирования - 8
Отправлено: Alder от Октябрь 24, 2008, 11:10:07
zer_owlet, напиши на php. Я думаю, что поймем код.


Название: Re: Искусство программирования - 8
Отправлено: LazarusLong от Октябрь 24, 2008, 11:29:59
Специально для него сделаю исключение и приму код на пхп )))


Название: Re: Искусство программирования - 8
Отправлено: Alexandr от Январь 16, 2009, 05:21:44
Если не будут гуглить, то смысл есть.
вот она подсказка к решению))


Название: Re: Искусство программирования - 8
Отправлено: artri от Январь 16, 2009, 10:04:18
Рискну предложить свое решение  :)
Код:
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();
        }
    }
}

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


Название: Re: Искусство программирования - 8
Отправлено: pfa от Январь 17, 2009, 11:23:56
Рискну предложить свое решение  Улыбка
Ужос...


Название: Re: Искусство программирования - 8
Отправлено: Storm от Январь 29, 2009, 11:51:29
Решение классика классикой ни компактное, ни красивое, ИМХО.... Но коль других уж нет...
Писал на 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 делать не обязательно было, но для алгоритма в целом этот момент важен.


Название: Re: Искусство программирования - 8
Отправлено: artri от Январь 30, 2009, 02:01:15
пошли алгоритмы, а то сплошной флейм и оффтоп :)