fentg.com

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

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


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


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



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

Регистриран на: Нед Ное 02, 2008 5:30 pm
Мнения: 3550
Такова е и заглавието на ИИД-то по проект "Успех"... /ИИД = Извънкласни и ИзвънУчилищни Дейности.../

Код:
Може ли да определите условието на задачата, чието примерно решение е на снимките по-долу?

Прикачени файлове:
1.png
Прикачени файлове:
2.png
Прикачени файлове:
3.png
Прикачени файлове:
4.png
Прикачени файлове:
5.png

................ следва ................

Прикачени файлове:
19.png


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

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


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

Регистриран на: Чет Авг 06, 2009 3:11 am
Мнения: 21
Аз мога да кажа условието :P


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

Регистриран на: Нед Ное 02, 2008 5:30 pm
Мнения: 3550
:super:
Ти си ясен, нали от тебе дойде това условие...
Нека младите се пробват, че имат малки проблеми с условията... ;)
:nazdrave:

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


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

Регистриран на: Чет Ное 27, 2008 12:06 am
Мнения: 111
А по-старите могат ли да се пробват :)


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

Регистриран на: Нед Ное 02, 2008 5:30 pm
Мнения: 3550
Абсолютно! Първо условието, и после... :bounce:

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


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

Регистриран на: Чет Ное 27, 2008 12:06 am
Мнения: 111
Условие: По въведено число от клавиатурата "N" да се състави двумерна матрица с N колони и N редове съдържаща целочислени стойности. Център на матрицата при нечетна стойност на N се явява нейният абсолютен център [N/2][N/2], а при четна стойност на N се взима [N/2][N/2-1] . Матрицата да бъде попълнена автоматично със последователни стойности , започвайки с единица от нейният център и запълвайки спираловидно в ред: нагоре, надясно, надолу, наляво.

Примерен код за решение на задачата:
Код:
#include <stdio.h>
#include <malloc.h>

void main() {
   int** matrix;
   int size;
   int idx;
   int max;
   int min;
   int row;
   int col;
   int number;
   
   printf("Enter matrix size: ");
   scanf("%d", &size);
   
   // Dynamic memory allocation
        /*
              Малко пояснение за указателите: Това са променливи, който сочат адрес в адресното пространство, на който се намира стойност от съответен тип. Обикновено са с големина 4 байта (зависи от големината на адресното пространство). Указателите се използват за динамично заделяне на памет, за адресна аритметика, за връщане на повече от 1 резултат от функция... Динамичната памет се заделя в Heap-а, за разлика от статичната, която се заделя в стека.
              Пример: int* a;
                          int b=2;

              В момента сме казали само, че имаме променлива а, която е указател и сочи към адрес, от където трябва да започне да чете int стойност. Тъй като не сме задали никаква стойност на "а", то тази променлива в момента сочи null и ако решим да присвоим стойност директно на нея това ще доведе до забиване на приложението.
              а = &b;
              Тук а взима адреса на b и следователно стойността зад указателя, която може да се достъпи с *а е 2;
              *а = 3;
              Записваме стойност 3 на адреса , който "а" сочи. Тъй като адреса, който сочи "а" е всъщност адресът на "b", след този ред и "b" ще има стойност 3.
              Пример за заделяне на памет динамично:
              int *a;

              a = (int *) malloc(sizeof(int));
              След като сме дефинирали "a", трябва да дадем на указателят някакъв адрес. В случая ще си заделим памет специално за него. За използването на malloc в повечето случаи, ще ви е нужна библиотеката <malloc.h>. Тя се грижи за организацията на паметта на heap-а. Кастваме заделената памет , като така казваме , че това е указател , който сочи стойност от тип int и запазваме памет за 1 елемент , който е с големина int. От тук нататък, вече имаме напълно инициализиран указател, на който може да се посочват стойности, които да записва на адреса към който сочи.
             Пример за заделяне на памет за масив динамично:
             int *a;
             int n;

             printf("Enter number n: ");
             scanf("%d", &n);

             a = (int *) malloc(sizeof(int)*n);
             Нещата са абсолютно идентични с това да се задели памет за 1 елемент , с разликата че тук просто умножавате големината на int с броя на елементите , които искате да имате в масива. Когато се обхожда масива трябва да се внимава да не излизате от границите на заделената памет, защото това ще доведе до срив в програмата. Тук следва малко адресна аритметика. Ако за "n" сме въвели примерно числото 4, то тогава ще сме заделили 16 последователни байта памет в heap-а , които можем да обходим, чрез указателят "a". *(а) взима стойността на първия елемент, *(а+1) на втория, *(а+2) на третия и *(а+3) на четвъртия. Не ни пречи да ползваме и индекси - a[0], a[1], a[2], a[3]. И двата начина имат абсолютно един и същи ефект.
            Пример за заделяне динамично на двумерен масив:
             int **a;
             int n;
             int idx;

             printf("Enter number n: ");
             scanf("%d", &n);

             a = (int **) malloc(sizeof(int*)*n);
             for(idx=0; idx<n; idx++)
                    a[idx] = (int *) malloc(sizeof(int)*n);

             Тук нещата стават по-интересни. Тук имаме указател, който сочи към указател , който сочи към памет , която съдържа int стойност. Нашият двумерен масив ще има n редове и n колони. Да приемем , че n = 4.Първо заделяме редовете, което става с редът "a = (int **) malloc(sizeof(int*)*n);". Този ред заделя в heap-a 16 последователни байта памет, в които се съдържат 4 указателя, които сочат към полета съдържащи int. Идва следващата стъпка - тъй като нито един от тези указатели в момента не сочи към нищо ние трябва за всеки един от тях да заделим памет. Това става с помощта на цикъла , в който заделяме памет за всеки един указател. За всеки един указател се заделят по 16 последователни байта , които ще съдържат в себе си по 4 Int стойности. Общо се заделят 64 байта за 4-те (int *) указателя, който обаче е много вероятно да не са последователни. В крайна сметка имаме заделени 80 байта в heap.
              а -> | *(a) | *(a+1) | *(a+2) | *(a+3) |
                     4 byte   4 byte    4 byte     4 byte
              a[0] == *(a) -> | a[0][0] | a[0][1] | a[0][2] | a[0][3] |
                                       4 byte     4 byte   4 byte      4 byte
              a[1] == *(a+1)-> | a[1][0] | a[1][1] | a[1][2] | a[1][3] |
                                         4 byte     4 byte    4 byte    4 byte
              a[2] == *(a+2)-> | a[2][0] | a[2][1] | a[2][2] | a[2][3] |
                                         4 byte     4 byte    4 byte     4 byte
              a[3] == *(a+3)-> | a[3][0] | a[3][1] | a[3][2] | a[3][3] |
                                         4 byte     4 byte     4 byte    4 byte

              След като сте приключили работа с динамично заделената памет е ваша отговорността да си я освободите. Това става с функцията free(). В случай като последния пример първо освобождавате указателите към Int и след това освобождавате указателя към указателите.
              Надявам се малко да съм пояснил нещата за динамичното заделяне на памет.
       */
   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;
   max = size;
   min = 0;
   
   if(size%2 == 1) {
      // Start from top left [0][0] to bottom
      row = 0;
      col = 0;
      
      while( min < max ) {
         
         while( row < max ) {
            matrix[row++][col] = number--;
         }
         row--;
         col++;
         while( col < max ) {
            matrix[row][col++] = number--;
         }
         col--;
         row--;
         while( row >= min ) {
            matrix[row--][col] = number--;
         }
         row++;
         col--;
         while( col > min ) {
            matrix[row][col--] = number--;
         }
         col++;
         row++;
         
         min++;
         max--;
      }   
   } else {
      // Start from bottom right [size-1][size-1] to top
      row = size-1;
      col = size-1;
      
      while( min < max ) {
         
         while( row >= min ) {
            matrix[row--][col] = number--;
         }
         row++;
         col--;
         while( col >= min ) {
            matrix[row][col--] = number--;
         }
         col++;
         row++;
         while( row < max ) {
            matrix[row++][col] = number--;
         }
         row--;
         col++;
         while( col < max-1 ) {
            matrix[row][col++] = number--;
         }
         col--;
         row--;
         
         min++;
         max--;
      }   
   }
   
   
   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;
}


Последна промяна Pulse на Пон Яну 13, 2014 1:42 pm, променена общо 1 път

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

Регистриран на: Нед Ное 02, 2008 5:30 pm
Мнения: 3550
Условието е приказно! Благодаря!

Ииии

Благодаря за кода, нооо

Много дълго решение... Моето е 16 реда... :bounce:

Къде бъркам? :bounce:

Като брой цикли имам само един for и никакви други?

Не ми се поства още кода тук, защото смятам да го вземем скоро с малко по-напредналите.

Надявам се твоят код да е тестван... Много ти благодаря още веднъж!

Къде и кога си решавал тази задача?

Като й гледам кода - на пръв поглед не е лесно и да бъде обяснен...

На мен ми трябваше около месец "улягане" на условието, докато стигна до идея...

Оттам - снощи за около 2 часа написах 16 реда код... 2 часа - заедно с тестването...

Харесва ми също, че и ти си я написал на чисто C... Аз също, но при тебе доста неща не ми са ясни - откъм езикови конструкции...

Както и да е - като изкарам моя код тук някой ден, придружен с обяснение ще си говорим/пишем пак...

През това време може да помислиш за оптимизация... Централна - на самия алгоритъм - от самата идея...

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


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

Регистриран на: Чет Ное 27, 2008 12:06 am
Мнения: 111
Всичко е въпрос на гледна точка :)

Явно сте се сетили за по-хитър и по-кратък подход :)

Сега го написах кода. Отне ми време от както писахте , че няма проблем и аз да се включа до когато публикувах кода. Тестван е кодът. Такива задачи сигурно съм решавал преди 4-5 години в първи курс, вече не помня. Но като цяло кодът е доста елементарен и ще си направя труда да едитна поста утре с повече и по-подробни коментари. Ще помисля и за оптимизация на кода , защото съм сигурен, че такава съществува. Моя код се базира на двата края , в които завършва тази матрица и спрямо края попълвам матрицата. Тоест правя нещата отзад напред ... по-лесно , но най-вероятно не толкова оптимизирано.


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

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

След определяне на началната позиция с две формули, вървящи и в четна и нечетна матрица започвам да пълня в единствен цикъл - for, който определя само съдържанието.

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

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

Определянето на следващия елемент е по-инересната и основна част от идеята: Движението винаги се осъществява в 4 последователно сменящи се посоки... Остава само да се разбере по колко стъпки се правят във всяка една от тях...
Така се търси еднозначно определена редица от числа - брой стъпки в поредна посока... КАто се открие тази редица и си на една крачка от финала - редицата е строго определена и лично аз срещнах проблем, поради загуба на форма да генерирам по достатъчно прост алгоритъм тази редица... След няколко опита в движение опростих нещата до броячи, които да се превъртат определен брой пъти на всяка итерация на основния и единствен цикъл...

Примерно - броячът за посоката заема последователно стойностите от 0 до 3 или от 1 до 4 - въпрос на кодировка на посоката с конструкцията:
Код:
direction=(direction+1)%4;
Това обуславя кодировка 0-3, за да не ползвам по-сложното:
Код:
if(direction%4)direction++;
else direction=1;
което ще ми даде 1-4... Но това са подробности... Важното е, че с такива броячи определям броя стъпки преди "завой на дясно", като и този брой стъпки нараства закономерно /редицата числа, за която писах/...
А при движение в определената посока имам едно малко swith-ленце с 4 case-а - какво става с индексите за всяка посока... И това е последното нещо, което се случва в цикъла, като преди това е определена посоката, която или е променена преди това в тази итерация или не е...

Дано идеята ми е ясна...

Допълнително изясняване - малко по-натам, ако някой мисли, че това вече е достатъчно добро предложение...

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


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

Регистриран на: Нед Ное 02, 2008 5:30 pm
Мнения: 3550
Като изключим алгоритъма,

кодът ти е идеален учебен пример за работа с динамична памет,

динамични масиви и самото заделяне и освобождаване на паметта...

Това е супер в случай, че искаш да работиш с масив, точно толкова голям, колкото е необходимо.

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

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

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

Колко хубаво би било, ако можеше този код да е истина:
/като за нашия случай/
Код:
main()
{unsigned N=100;
    unsigned a[N][N];
    ...................
т.е. да се обяви размерността на масива с променлива... което би довело и до възможността тази променлива да получи стойност от потребителя...

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

И понеже на тази задача алгоритъма е по-важен от тези неща - смятам, че ако задам
Код:
unsigned a[50][50];
предварително, това едва ли би било огромна загуба на памет в случаите, когато N е доста малко... Вярно е, че това все пак е ограничаващо, но с учебна цел пък и поради екранни ограничения...

Ако вместо
Код:
%d\t
използваш
Код:
%4d
примерно, ще имаш и дясно подравняване на числата за по-красиво и по-пестеливо...

Но всичко това са подробности... Изключително съм горд на единствения си for... :peace:

Все пак близо месец, откакто Чефо дойде и ми "подхвърли" условието... И то зрееше в главата ми...

В интерес на истината, в началото и на мен ми мина вариант - отвън - навътре, който ми се стори по-лесен за осъществяване... Доста късно, след като ми се стори неефективно се разделих с този вариант...

Но най-добре ще е да се види кода - да се обясни и така...

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

Много ми е интересно - ти къде и как се научи на това... Сподели, ако може... Благодаря!

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


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

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


Кой е на линия

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


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

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