Млад разработчик...

Pulse · **Публикувано на:** Пон Яну 13, 2014 12:28 am

Относно алгоритъма , разбрах идеята ви и я написах по вашия начин. Тествах и работи . Ще ви пратя кода на лично съобщение , за да не ви бъркам учебния материал и някой впечатления след като ги потвърдя :)

mitko · **Публикувано на:** Пон Яну 13, 2014 12:56 am

emilang написа:

Значи - първото нещо в цикъла е поставянето на стойността в елемента.

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

emilang · **Публикувано на:** Пон Яну 13, 2014 1:27 am

Ейй, Митаче!

Жив и Здрав!

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

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

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

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

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

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

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

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

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

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

Успех!

mitko · **Публикувано на:** Пон Яну 13, 2014 1:55 am

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

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

emilang · **Публикувано на:** Пон Яну 13, 2014 2:28 am

Формулите за изчисляване на "центъра" са супер елементарни и са само едни - без значение дали N е четно или не...

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

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

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

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

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

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

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

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

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

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

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

Та така...

Pulse · **Публикувано на:** Пон Яну 13, 2014 10:31 am

Идеята, която 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 , всеки друг език от там нататък се усвоя за по-малко от месец на доста по-добро ниво. Обратната ситуация не важи. :)

emilang · **Публикувано на:** Пон Яну 13, 2014 1:09 pm

Много ти благодаря за хубавия отговор...

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

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

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

Pulse · **Публикувано на:** Пон Яну 13, 2014 1:50 pm

http://www.soft-press.com/goto.htm?http ... ewbook=100

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

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

emilang · **Публикувано на:** Пон Яну 13, 2014 2:49 pm

Идеален си!

Много!

:nazdrave:

mitko · **Публикувано на:** Пон Яну 13, 2014 5:38 pm

Pulse написа:

Ако се научи C , всеки друг език от там нататък се усвоя за по-малко от месец на доста по-добро ниво. Обратната ситуация не важи. :)

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

fentg.com

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

Млад разработчик...

Кой е на линия