fentg.com

ФОРУМЪТ на ФЕНОВЕТЕ на НТГ
Дата и час: Нед Апр 11, 2021 7:45 am

Часовете са според зоната UTC + 2 часа [ DST ]


Правила на форума


Натиснете за да видите правилата



Напиши нова тема Отговори на тема  [ 26 мнения ]  Отиди на страница Предишна  1, 2, 3  Следваща
Автор Съобщение
 Заглавие: Re: Млад разработчик...
МнениеПубликувано на: Пон Яну 13, 2014 12:28 am 
Offline
Аватар

Регистриран на: Чет Ное 27, 2008 12:06 am
Мнения: 111
Относно алгоритъма , разбрах идеята ви и я написах по вашия начин. Тествах и работи . Ще ви пратя кода на лично съобщение , за да не ви бъркам учебния материал и някой впечатления след като ги потвърдя :)

_________________
Ако нямаш приятели в живота, все едно да живееш в къща върху пясък!
Изображение
http://www.vergov.com


Върнете се в началото
 Профил  
 
 Заглавие: Re: Млад разработчик...
МнениеПубликувано на: Пон Яну 13, 2014 12:56 am 
Offline

Регистриран на: Сря Ное 19, 2008 5:48 pm
Мнения: 513
emilang написа:
Значи - първото нещо в цикъла е поставянето на стойността в елемента.


Няма ли да е по-добре, това да е последното нещо което се прави?
В смисъл почваш от число N^2 и в зависимост дали N е четно или нечетно, почваш от елемент [0][0] или [N-1][N-1].
Началната ти посока е надолу и в цикъла имаш 4 иф-а като във всеки има иф елс конструкция:
ако посоката е надолу проверяваме дали долния елемент е свободен и ако е свободен го запълваме и брейкваме, в противен случай променяме посоката на дясно, след това аналогичното го правим още 3 пъти за другите посоки и на практика попълваш масива отвън на вътре.

_________________
Toва което не може да се опише с думи, се описва с музика.


Върнете се в началото
 Профил  
 
 Заглавие: Re: Млад разработчик...
МнениеПубликувано на: Пон Яну 13, 2014 1:27 am 
Offline
Администратор
Аватар

Регистриран на: Нед Ное 02, 2008 5:30 pm
Мнения: 3550
Ейй, Митаче!

Жив и Здрав!

Имаш идеи, но самият факт да проверявам дали е свободен или зает е противно на идеята ми - аз се движа по строг еднозначен маршрут и запълвам точно N*N елемента, ако броим от единица /не от 0/ и само би усложнил - това е идея за друг тип задачи - примено да не повтаряш откъдето си минал, ако маршрута не може да се зададе строго, докато в нашият случай съм открил, че маршрута може да бъде описан еднозначно...

И понеже "началният адрес" го задавам преди цикъла, затова решавам в него - първата ми стъпка - да е да "пълня"...

И после да изчислявам адреса на следващия елемент...

Ако се опиташ да изведеш индуктивно числова редица с бройки стъпки в една посока последователно, ще видиш, че редицата има строга описвателност и понеже последният елемент се опитва да бъде "извън закона" на редицата, се радвам, че ще бъде "напълнен" преди да бъде определен следващият погрешно... и ще се излезе от цикъла...

Тази радост е и затова, че редицата се подчинява на този сравнително прост за описване закон - от центъра към периферията... Обратно бе по-сложно...

Сиян е допуснал неточност в определяне на индексите на началния елемент там където е описал условието на задачата... Аз ги определям по формули, които са еднозначни, независимо от четността на N, без условност...

Както и да е - като имаш идея е редно да видиш дали е осъществима и на каква цена...

Ако не си забравил - може да пробваш...

БТВ - с компилатор, вграден в средата DEV-C++ спокойно може да се пропуска "инклудване" на библиотеките...

А на този адрес съм сложил преносимата Dev-C++ 4.9.9.2 Portable версия...

Успех!

_________________
Изображение


Върнете се в началото
 Профил  
 
 Заглавие: Re: Млад разработчик...
МнениеПубликувано на: Пон Яну 13, 2014 1:55 am 
Offline

Регистриран на: Сря Ное 19, 2008 5:48 pm
Мнения: 513
Ами на този алгоритъм, който предложих ми харесва това, че не ме интересува къде е единицата, тоест къде свършва запълването, защото алгоритъма сам си го намира. Другото което ми допада е това, че не ме интересува от къде ще защочне запълването, тоест при четни и нечетни N за алгоритъма няма значение, та дори да се почне от средата на ред пак няма значение. Идеята ми беше да се запълва винаги "долепен до стената" и малко по-малко бива заклещен сам от себе си.
Недостатъка е , че малко по-трудно ще се изпълни статично , след като нямаме точно определен масив, а и при C/C++ доколкото си спомням, когато се създе масив елементите му не са =NULL , така че, така или иначе трябва да се нулират предварително. Другото което е, чисто логически , ако почнеш от вън навътре трябва предварително да знаеш размерноста на масива, защото самата идея на алгоритама е, размерноста да те ограничава, докато по твоя начин, когато се почва от вътре навън, на практика не те интересува кога ще спреш, защото нищо не те ограничава.

Иначе не съм ти видял точно алгоритъма, но ми се струва че моя ще е малко по-разбираем, защото е изключително прост - цикъл с 4 иф-а с по иф елс конструкция във всеки, без нищо друго. Самата идея, че трябва по формули да изчисляваш от къде да почнеш, не ми допада, но както каза Pulse всичко е въпрос на гледна точка и как всеки ще приеме проблема, особено като се има предвид, че задачата е много лесна и ако успееш да намериш алгоритъм с по-голяма от линейна сложност си направо герой :D

_________________
Toва което не може да се опише с думи, се описва с музика.


Върнете се в началото
 Профил  
 
 Заглавие: Re: Млад разработчик...
МнениеПубликувано на: Пон Яну 13, 2014 2:28 am 
Offline
Администратор
Аватар

Регистриран на: Нед Ное 02, 2008 5:30 pm
Мнения: 3550
Формулите за изчисляване на "центъра" са супер елементарни и са само едни - без значение дали N е четно или не...

В моята реализация има един фор и два ифа - единият иф е с елз, другият е чист и прост - двата ифа са във фора, като имам и един суич с 4 кейса за посоките...

Ако става въпрос за обясняване - ето как се сещам, че бих ти го обяснил:

Седиш с вързани очи в центъра на квадратно помещение - това са ти го разправяли преди да те вкарат.
Казали са ти, че пътят към изхода е "спираловиден", но с коридори, разположени под прав ъгъл един спрямо друг...
Дават ти шанс да се спасиш, ако излезеш без да докоснеш стена /защото стените са безкрайно тънки/ и са ти казали само, че ширината на коридор е точно една твоя крачка и излизането е по часовата стрелка - т.е. имаш само десни завои...

Ти си седнал в правилната посока за тръгване. /този, който те е оставил, те е разположил с лице в правилна посока/

Преди да станеш, разсъждаваш наум и си правиш план - ставам, правя една крачка напред, завивам, пак една напред, пак завивам, после една или две напред (дали вече не съм на изхода), завивам и т.н...

Планът ти изплува в съзнанието кристално ясен. Ставаш, тръгваш и следвайки точно плана - излизаш...
Разчиташ само, че като стъпиш точно на изхода, веднага ще свалят превръзката от очите ти /това са ти го обещали/ и затова броя обиколки не те интересува. Правиш само един трик - през два завоя, като си направиш нужните крачки се спираш и ако няма признаци, че си на изхода (никой не ти сваля превръзката) - то тогава правиш още една крачка и тогава завиваш...

Ако мислиш, че това е лесно за досещане - гледайки спиралния коридор - скициран отгоре - това на фантазия, докато си седиш с вързани очи... ;) то моят алгоритъм следва точно този маршрут... Имаш само смятане на брой крачки, завой след завой те стават повече и повече, но следват точен закон за нарастване... И трикът - ако не си точно на изхода - значи имаш още една крачка напред и тогава още два завоя с нужните крачки...

Ясно е, че с всяка крачка стъпваш точно в/у един елемент на масива. Всяка твоя стъпка е една моя итерация на фор-а...

И последно - всяко по-малко N е "вписано" в следващото (има и рекурсивен вариант за решаване)...
Т.е. ако си смяташ колко е дотук N по време на движението и още не си излязъл - имаш цели 2 коридора за изминаване. Пак спираш, ослушваш се, още една крачка напред и още два коридора дълги колкото последния и пак спиране, изчакване и т.н. ...

Бая рисунки ми минаха през скициране и се сетих за цялата тази приказка...

Та така...

_________________
Изображение


Върнете се в началото
 Профил  
 
 Заглавие: Re: Млад разработчик...
МнениеПубликувано на: Пон Яну 13, 2014 10:31 am 
Offline
Аватар

Регистриран на: Чет Ное 27, 2008 12:06 am
Мнения: 111
Идеята, която mitko е написал реално е подобна на тази, която е реализирана с първия алгоритъм, който съм написал. Разликата е, че проверката се извършва от самият вътрешен цикъл, а не от if-клаузи.

Втора реализация спрямо идеята на г-н Ангелов:
Код:
#include <stdio.h>
#include <malloc.h>

void main() {
   int** matrix;
   int size;
   int idx;
   int row;
   int col;
   int number;
   int direction;
   
   printf("Enter matrix size: ");
   scanf("%d", &size);
   
   // Dynamic memory allocation
   matrix = (int **) malloc(sizeof(int*)*size);
   for(idx=0; idx<size; idx++)
      matrix[idx] = (int *) malloc(sizeof(int)*size);
   
   // Init matrix;
   for(row=0; row<size; row++)
      for(col=0; col<size; col++)
         matrix[row][col] = 0;
   
   number = size*size;
   if(size%2 == 1) {
      row = size/2;
      col = size/2;
   } else {
      row = size/2;
      col = size/2-1;
   }
   
   direction = 0;
   for(idx = 1; idx <= number; idx++) {
      switch(direction) {
         case 0: matrix[row--][col] = idx; break;
         case 1: matrix[row][col++] = idx; break;
         case 2: matrix[row++][col] = idx; break;
         case 3: matrix[row][col--] = idx; break;
      }
      
      if (row < 0) row = 0;
      if (col < 0) col = 0;
      if (row >= size) row--;
      if (col >= size) col--;
      if (direction == 0 && matrix[row][col+1] == 0) direction++;
      else if(direction == 1 && matrix[row+1][col] == 0) direction++;
      else if(direction == 2 && matrix[row][col-1] == 0) direction++;
      else if(direction == 3 && matrix[row-1][col] == 0) direction = 0;
   }   
      
   for(row=0; row<size; row++) {
      printf("\n");
      for(col=0; col<size; col++)
         printf("%d\t", matrix[row][col]);
   }
   
   // Free memory
   for(idx=0; idx<size; idx++)
      free(matrix[idx]);
   free(matrix);
      
   return;
}


Сега ще се опитам да я оптимизирам и да получа крайният негов алгоритъм пък да видим до къде ще я докарам :)

Видях , че сте ме попитали от къде съм се научил. Общо взето миналата година завърших ТУ-София, ф-л Пловдив и съм Инженер КСТ и сега съм магистър същата специалност :) Такива работи учихме първи курс когато те карат да си шаваш мозъка и да почнеш да мислиш алгоритмично. Неизменен помощник през всичките години ми остана една книжка на C от софтпрес , но по-старо издателство (бяла с малко червенко) . Безценна книжка, която обяснява всичко на доста добро ниво. Ако някой има интерес да се занимава с програмиране го съветвам да почне от там. Ако се научи C , всеки друг език от там нататък се усвоя за по-малко от месец на доста по-добро ниво. Обратната ситуация не важи. :)


Върнете се в началото
 Профил  
 
 Заглавие: Re: Млад разработчик...
МнениеПубликувано на: Пон Яну 13, 2014 1:09 pm 
Offline
Администратор
Аватар

Регистриран на: Нед Ное 02, 2008 5:30 pm
Мнения: 3550
Много ти благодаря за хубавия отговор...

Ако може да поставиш една снимка на корицата на тази книга - бялата с малко червенко... Да я видим коя е?

И до скоро - Успех по темата и навсякъде!

Най-ми допадна идеята за мърдането на мозъците... :nazdrave:

_________________
Изображение


Върнете се в началото
 Профил  
 
 Заглавие: Re: Млад разработчик...
МнениеПубликувано на: Пон Яну 13, 2014 1:50 pm 
Offline
Аватар

Регистриран на: Чет Ное 27, 2008 12:06 am
Мнения: 111
http://www.soft-press.com/goto.htm?http ... ewbook=100

Това е книжката. Не знам дали още я издава, защото май имат някакъв по нов вариант, който обаче май е структуриран по различен начин.

Променил съм поста с първия вариант на кода като съм се опитал да обясня максимално просто и ясно идеята на динамичното заделяне поне за тази задача.

_________________
Ако нямаш приятели в живота, все едно да живееш в къща върху пясък!
Изображение
http://www.vergov.com


Върнете се в началото
 Профил  
 
 Заглавие: Re: Млад разработчик...
МнениеПубликувано на: Пон Яну 13, 2014 2:49 pm 
Offline
Администратор
Аватар

Регистриран на: Нед Ное 02, 2008 5:30 pm
Мнения: 3550
:dizzy:

Идеален си!

Много!

:nazdrave:

_________________
Изображение


Върнете се в началото
 Профил  
 
 Заглавие: Re: Млад разработчик...
МнениеПубликувано на: Пон Яну 13, 2014 5:38 pm 
Offline

Регистриран на: Сря Ное 19, 2008 5:48 pm
Мнения: 513
Pulse написа:
Ако се научи C , всеки друг език от там нататък се усвоя за по-малко от месец на доста по-добро ниво. Обратната ситуация не важи. :)


Е ако беше казал C++, щеше да се съглася, но от C да преминеш на някой обектно ориентиран език, не е най-лесната задача, защото концепциите на процедурното и обектно ориентираното програмиране са доста различни. Направо трябва да си смениш начина на мислене, за да преминеш от 1-то на другото.

_________________
Toва което не може да се опише с думи, се описва с музика.


Върнете се в началото
 Профил  
 
Покажи мненията от миналия:  Сортирай по  
Напиши нова тема Отговори на тема  [ 26 мнения ]  Отиди на страница Предишна  1, 2, 3  Следваща

Часовете са според зоната UTC + 2 часа [ DST ]


Кой е на линия

Потребители разглеждащи този форум: 0 регистрирани и 1 госта


Вие не можете да пускате нови теми
Вие не можете да отговаряте на теми
Вие не можете да променяте собственото си мнение
Вие не можете да изтривате собствените си мнения
Вие не можете да прикачвате файл

Иди на:  
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
Превод: Ioan Filipov