• Здраво и добредојдовте на форумот на IT.mk.

    Доколку сеуште не сте дел од најголемата заедница на ИТ професионалци и ентузијасти во Македонија, можете бесплатно да се - процесот нема да ви одземе повеќе од 2-3 минути, а за полесна регистрација овозможивме и регистрирање со Facebook и Steam.

Aлгоритми

  • Ја почнал/а темата
  • #1

maximilian

Gaining Experience
26 март 2008
1,064
74
Не најдов тема тука каде што би споделиле некои алгоритми, па еве да отворам една :). Тука постирајте алгоритми, и за каква намена се користат истите. Објаснете ги алгоритмите на природен јазик, а пожелно е и потоа да го напишете како пример со било кој програмски јазик (колку повеќе јазици, толку подобро).
Навалете! :)

EDIT: Доколку сакате, можете пример алгоритмите што некој ги постирал во одреден програмски јазик, да го преведете во друг, со што и би му скратило на време на тој што ги учи, а не го познава јазикот во кој се примерите.
 
  • Ја почнал/а темата
  • #2

maximilian

Gaining Experience
26 март 2008
1,064
74
Алгоритам за сортирање - Selection Sort

Сортирањето на одреден тип на податоци е многу чест проблем во програмирањето. Имено, кога создавате некоја база од податоци, или може и да е и обична низа, понекогаш се јавува потреба да се сортираат елементите кои се од ист тип, со што би се олеснило читањето и обработката на податоците од самиот корисник. Алгоритми за сортирање има многу. Јас сега ќе пробам да го објаснам алгоритамот наречен Selection Sort.

Значи, имаме една низа, составена од ист тип елементи, која се состои од n елементи. За индексирање на елементите најчесто се користи променливата i, затоа и ние ќе ја користиме во овој пример. Алгоритамот е следниот:
Прво декларираме две променливи од тип на целите броеви што ќе ни служат како индекси: i и ј.
Сега користиме вложени циклуси:
за i=0 до n-1 повторувај
за ј=i+1 до n повторувај
ако (а>a[j])
тогаш замени ги местата на а и a[j]

Да го анализираме алгоритамот. Значи прво, од кога се декларираат променливите i и j, кои служат за индекси на низата, правиме еден вложен циклус. Вложениот циклус се состои од двата циклуса:

за i=0 до n-1 повторувај

и

за ј=i+1 до n повторувај

Тоа се користи за да се споредуваат два елемента во низата. Значи, кога на пример i=0, тогаш ј=1,2,3,...n. Кога i=1, тогаш ј=2,3,...n. И на крајот, кога i=n-1, j=n. Со тоа се исцрпуваат сите членови од низата. Е сега, во вложениот циклус, имаме услов, доколку а>a[j], тогаш користиме веќе создадена функција за размена на елементи која ќе им ги смени местата на a и a[j].

Значи, фактички овој алгоритам селектира еден елемент, и го споредува со секој друг елемент од низата. Ако тој елемент е поголем од другиот, тогаш двата елемента си ги сменуваат местата. Така елементите се сортираат од најмалиот кон најголемиот. Ако имаме потреба да се сортираат елементите од најголемиот кон најмалиот, тогаш само во условот “ако“ знакот > го заменуваме со знакот <.

Пример: Нека “а“ е низа од 10 елемента (n=10), кои се цели броеви. Доколку ја воведеме низата со следните елементи:
15 37 85 31 14 2 95 34 24 17

и доколку се искористи овој алгоритам, резултатот на програмата ќе биде:
2 14 15 17 24 31 34 37 85 95.

Алгоритамот представен во јазикот С++ изгледа вака:
Код:
 int i,j;
          for (i=0 ; i<9; i++)
               for (j=i+1 ; j<10 ; j++)
                   if (a[i]>a[j])
                      swap(&a[i],&a[j]);
каде што swap ни е функција која им ги менува местата на двата члена.

Source за целосната програма во С++:
Код:
#include<iostream>
#include<stdlib.h>

using namespace std;

void swap (int*, int*);

int main()
{
    int a[10];
    for (int i=0; i<10; i++)
        {
             cout << "a[" << i << "]=";
             cin >> a[i];
        }
    for (int i=0; i<10; i++)
        cout << a[i] << " ";
    cout << "n";
    
    int i,j;
           for (i=0 ; i<9; i++)
               for (j=i+1 ; j<10 ; j++)
                   if (a[i]>a[j])
                      swap(&a[i],&a[j]);
    for (int i=0; i<10; i++)
        cout << a[i] << " "; 
    cout << "n";
    system ("pause");
    return 0;
}

void swap(int*x, int*y)
{
 int t=*x;
 *x=*y;
 *y=t;
}
 

loverboy

Intern
6 февруари 2008
147
11
Алгоритмите се многу општа тема. Тоа е посебна наука. За алгоритми би требало да се направи цел форум, а не само тема :) Мислам дека е подобро да се постираат директни линкови до местата на интернет каде што се објаснети алгоритмите, а и линкови до книги кои ги објаснуваат сите најчесто користени и најдобри алгоритми од сите подобласти на алгоритмите. На пример:
Introduction to algorithms
The Art of Programming
Programming Design Manual
Programming Challenges
Programming in C
и многу други. Овде е најдобро да се објават линкови до овие книги и до многу други. Ова се само неколку на кои во овој момент се сеќавам.
Премалку е една тема да има за да се пишуваат описи на алгоритмите (плус дискусија) :)
Само за разните алгоритми за сортирање малку се 30 постови.
bubble sort, insertion sort, selection sort, shell sort, heap sort, merge sort, quick sort, radix sort...
Значи мој предлог, тема каде што ќе се ставаат линкови до објаснувања на алгоритми (ги има многу на интернет) плус линкови од книги. А плус ова да биде и место каде што ќе има дискусија околу алгоритмите, нивна анализа, ако има нешто нејасно и слично.
Поздрав :)
 
  • Ја почнал/а темата
  • #4

maximilian

Gaining Experience
26 март 2008
1,064
74
@loverboy

Во право си за се што кажа погоре, но мислам дека вреди да пробаме, да видиме како ќе се одвиваат работите. Доколку е премалку оваа тема, админите може да додадат и под-форум за ова па да се среди тој проблем така :). А мислам дека на сите би ни одговарало да размениме знаења и искуства околу оваа тематика, секој може да научи нешто ново, а и да му се најде понатаму во професионалната кариера, а и секој може да каже нешто што го знае, за и другите да го научат. :)
 

Blagojce

Gaining Experience
26 декември 2007
889
69
Прилеп
Blagojce's setup  
Processor & Cooler
Intel Core i5-3570 3.40GHz
Storage
2 TB
RAM
8 GB
Monitor
ASUS 24" LED Full HD
OS
Windows 10
Баш сега го учиме тоа на fax и за овој алгоритам од maximilian мислам дека би изгледал вака:


Мене потешко ми оди со алгоритмиве бидејќи до сега немам решавано ниеден, а сега браво за maximiian што ја отвори темава ќе може да размениме искуства.:)
 
  • Ја почнал/а темата
  • #6

maximilian

Gaining Experience
26 март 2008
1,064
74
Алгоритам за НЗД - алгоритамот на Евклид

Сега ќе го објаснам алгоритамот на Евклид за наоѓање на НЗД. Овој aлгоритам има огромно историско значење за алгоритмиката, затоа што е еден од најстарите алгоритми што човештвото го знае, се појавил некаде околу 300 г.п.н.е. Евклид всушност го формулирал проблемот геометриски, како проблем за наоѓање на најголема заедничка должина за две отсечки.

Алгоритамот се состои од следново:

Земаме две променливи а и b, кои се цели броеви и треба да го најдеме нивното НЗД.
1) додека а е различно од b (a!=b) повторувај
2) ако (а>b) тогаш, a=a-b
3) ако (а<b) тогаш, b=b-a

Резултатот е во а. Значи додека (a!=b) и ако а>b, тогаш а=а-b, a доколку a<b, тогаш b=b-a. Доколку a=b, тогаш алгоритамот свршува. Просто, нели? :)

Овој алгоритам во С++ би изгледал вака:
Код:
int gcd (int a, int b)
{
    while (a!=b)
          if (a>b)
             a=a-b;
             else
                 b=b-a;
    return a;
}
Тоа е итеративното решение. Да го разгледаме рекурсивното решение.
Доколку (a!=b) тогаш повторувај
ако а>b тогаш извикај функција gcd (т.е. самата функција) со параметрите (a-b, b)
ако а<b тогаш извикај функција gcd (т.е. самата функција) со параметрите (а, b-a)

Рекурсивниот алгоритам на Евклид за НЗД во С++ би изгледал вака:

Код:
int gcd(int a, int b)
{
     if (а==b)
         return a;
     if  (a>b)
         return gcd(a-b,b);
     if  (a<b)
         return gcd(a, b-a);
}
 

Fiasco

Gaining Experience
2 март 2008
3,036
203
404
www.igorjanevski.com
Гледам Благојче постирал блок дијаграм, па доколкиа некои што не знаат а ги интересира еве мало објаснување за овие дијаграми.

 

TataMata

Intern
13 јуни 2008
115
1
Maximilian малку направи го поопшт алгоритамот за НЗД, т.е. не за 2 броеви него да наоѓа НЗД за n броеви.
 
1 октомври 2008
278
9
пресметување на престапна година :

1. Внесување на година (god)
2. Obrabotka na Podatok (delenje so ostatok)
3. споредување
4. печатење на екран

Код:
program prestapna;

var god:integer;
begin
readln(god)
if god mod 4 = 0 then 
writeln('prestapna e');
else
writeln('ne e prestapna');
end if
end.
Код:
private function prestapna(byval god as integer)
Input (god)
if god mod 4 = o then 
msgbox("prestapna e")
else 
msgbox("ne e prestapna")
end if
end sub 
call prestapna(2037)
Код:
#include stdio.h
#include math.h
void prestapna();
int main(){
prestapna(1239);
}
int prestapna(int god)
if god mod 4 = 0 {
printf("prestapna e");
}
else {
printf("ne e prestapna");
}
}
 

vik

Intern
14 април 2007
1,936
31
Maximilian малку направи го поопшт алгоритамот за НЗД, т.е. не за 2 броеви него да наоѓа НЗД за n броеви.
Не сум сигурен ама мислам дека напишаното е Ефклидов алгоритам.
Иначе за повеќе броја не би требало да е многу комплицирано, ама за оптимизација... тоа е веќе надвор од мое познавање.:)
 

vasildb

Intern
17 април 2007
209
6
пресметување на престапна година :

1. Внесување на година (god)
2. Obrabotka na Podatok (delenje so ostatok)
3. споредување
4. печатење на екран

Код:
program prestapna;

var god:integer;
begin
readln(god)
if god mod 2 = 0 then 
writeln('prestapna e');
else
writeln('ne e prestapna');
end if
end.
Код:
private function prestapna(byval god as integer)
Input (god)
if god mod 2 = o then 
msgbox("prestapna e")
else 
msgbox("ne e prestapna")
end if
end sub 
call prestapna(2037)
Код:
#include stdio.h
#include math.h
void prestapna();
int main(){
prestapna(1239);
}
int prestapna(int god)
if god mod 2 = 0 {
printf("prestapna e");
}
else {
printf("ne e prestapna");
}
}
Престапна година е секоја година која е делива со четири, а не со два. И во C++ тоа мислам дека не се прави со mod туку со %.
 

vasildb

Intern
17 април 2007
209
6
Заборавив, и споредба со два знаци за еднакво се прави "==".

Значи
Код:
#include stdio.h

void prestapna();

int main()
{
    prestapna(1239)?printf("Prestapna"):printf("Ne e prestapna");
}

bool prestapna(int god)
{
    return god%4==0;
}
 

fuUuUzZzZy

On your way to fame
14 декември 2007
4,842
885
Ohrid
Алгоритам за пресметување збир на секој четири цифрен број


Еве еден школски пример за пресметување збир на секој четири цифрен број.

Објаснувањето ќе го почнам со пример:

Земаме еден четирицифрен природен број n. Во случајов ќе го земам 6572.

n = 6572

1. Бројот го делиме со 1000:

6572:1000=6 ( n Div 1000 )
572 ( n Mod 1000 )



2. Модот го делиме со 100:

572:100=5
72 ( n Mod 1000 Div 100 )

3. Модот го делиме со 10:

72:10=7 ( n Mod 1000 Mod 100 Div 10 )
2 ( n Mod 1000 Mod 100 Mod 10 )

Значи:

I <-- n Div 1000
S <-- n Mod 1000 Div 100
D <-- n Mod 1000 Mod 100 Div 10
E <-- n Mod 1000 Mod 100 Mod 10

____________________________________________

Школски поставен:

Алгоритам Број;
Почеток

Печати (`Внеси четирицифрен природен број ` );
Читај (n)

i <-- n Div 1000 ;
s <-- n Mod 1000 Div 100 ;
d <-- n Mod 1000 Mod 100 Div 10 ;
e <-- n Mod 1000 Mod 100 Mod 10 ;
vk <-- i + s + d + e ;

Печати (` Во бројот `,n,` вкупно има `,i,` илјади `,s,` стотки `,d,` десетки `,e,` единици и вкупно изнесува `,вк,`);

крај.


Ова е за 4 цифрен, истата постапка можете да ја примените и за повеќе или помалку цифрени броеви. Всушност со постапкава се одделуваат цифрите по единици, стотки, десетки.. Вака поделени, можете различно да ги искористите.



ps. Ако може некој да ме потсети како беше за изоставување цифра од повеќе цифрен број?

На пример:

Алгоритам за да се изостави четвртата цифра, и на крај да се испише целиот број без четвртата цифра

n = 234567
k = 4

После извршувањето, треба да се испечати 23567.
 
1 октомври 2008
278
9
Заборавив, и споредба со два знаци за еднакво се прави "==".

Значи
Код:
#include stdio.h

void prestapna();

int main()
{
    prestapna(1239)?printf("Prestapna"):printf("Ne e prestapna");
}

bool prestapna(int god)
{
    return god%4==0;
}
хехе добро оптимизирано .. бтв го пишував постот без компајлер а у ц/ц++ не сум програмирал одамна па имам забраено некои работи
 
  • Ја почнал/а темата
  • #16

maximilian

Gaining Experience
26 март 2008
1,064
74
Maximilian малку направи го поопшт алгоритамот за НЗД, т.е. не за 2 броеви него да наоѓа НЗД за n броеви.
Алгоритамот си е сосема општ, и може да се употреби на n броја. Финтата е шо ќе најдеш НЗД на првите два елемента. После, бараш НЗД од добиениот резултат и наредниот број, и тн. додека не ја исцрпиш целата низа од броеви. And that's it :)
 
  • Ја почнал/а темата
  • #17

maximilian

Gaining Experience
26 март 2008
1,064
74
Иначе, спиро_дт, алгоритамот за престапна година ти е погрешен. За да биде една година престапна, не е единствен услов таа да биде делива со 4. Значи, ако е делива со 4, тогаш не треба да биде делива со 100, или да биде делива со 400.

Т.е. Ако (година е делива со 4 и година не е делива со 100) тогаш годината е престапна
иначе ако годината е делива со 400, тогаш годината е престапна. Во сите останати случаи е непрестапна.

Кодот во С++:
Код:
if ((year % 4) == 0) && ((year % 100) != 0)) || ((year % 400) == 0)
 year = 1; //каде year=1 е вредност доколку годината е престапна, a ако year=0, тогаш е непрестапна
 else 
      year=0;
 

TataMata

Intern
13 јуни 2008
115
1
Алгоритамот си е сосема општ, и може да се употреби на n броја. Финтата е шо ќе најдеш НЗД на првите два елемента. После, бараш НЗД од добиениот резултат и наредниот број, и тн. додека не ја исцрпиш целата низа од броеви. And that's it :)
Нема да е баш ефикасно, мислам дека ќе се согласиш.
 

dime

Intern
13 мај 2008
163
3
Алгоритам за сортирање - Selection Sort

Сортирањето на одреден тип на податоци е многу...
Cisto sugestija, nemoj da se nalutis - gledaj sto pokratki postovi da pisuvas. Kako si trgnal ti kniga od 1000 strani ke se napise samo za site razni sortovi :) Zboruvam za analizata na detalite okolu implementacijata, inaku vovedot bas mi se dopagja. Eve jas na sto bi go svedil tvojot post:

Selection sort raboti taka sto se izbira i otstranuva minimalniot/maksimalniot element od listata sto treba da se sortira i se dodava na rezultatot se dodeka originalnata lista ne se isprazni.

Time/memory complexity: neka odredat ostanatite clenovi za vezba. Ali najverojatno treba prvo nekoj post da se napise za complexity i landau notation :)

Programski kod: ova voopsto ne treba! Kolku sto razbrav ova e tema za algoritmi, a ne voved vo programiranje ;-) Mozda pseudo code, ali za vakov prost sort ne gledam pricina da se trosi vreme na pisuvanje bilo kakvi kodovi. Moze ostanatite sto se zainteresirani da napisat kod za algoritamot i da go postiraat, taka temata ke bide pointeraktivna i pointeresna.
 
  • Ја почнал/а темата
  • #20

maximilian

Gaining Experience
26 март 2008
1,064
74
Нема да е баш ефикасно, мислам дека ќе се согласиш.
Не, токму напротив. Алгоритамот е солиден според мене. Затоа што за него се потребни n*4 B меморија + 8 B меморија за наоѓање на целосниот НЗД, затоа што функцијата има само 2 параметра, а знаеме дека таа работи со копијата на променливите и по завршувањето на истата, се ослободува стековата рамка на функцијата, т.е. се ослободува таа меморија, а се враќа резултатот во главната функција. И плус уште 4 В за една променлива која ќе ја зачуваува вредноста на секој најден НЗД на претходните два елемента, т.е.

декларираме променлива p која ја иницијализираме да биде првиот елемент од низата, т.е. p=a[0];.
Потоа, правиме циклус: за i=1 до i<n повторувај:
p=gcd(p, a);
i=i+1;

And that's it :). По излегувањето од циклусот резултатот се содржи во променливата p.

@dime:

Фала многу за добронамерните сугестии, ќе гледам да ги применам :)
 

Нови мислења

Последни Теми

Статистика

Теми
43,506
Мислења
822,118
Членови
28,046
Најнов член
hittrajkovski
На врв Дно