Aлгоритми

[maximilian]

Не најдов тема тука каде што би споделиле некои алгоритми, па еве да отворам една . Тука постирајте алгоритми, и за каква намена се користат истите. Објаснете ги алгоритмите на природен јазик, а пожелно е и потоа да го напишете како пример со било кој програмски јазик (колку повеќе јазици, толку подобро).
Навалете!

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

 

[maximilian]

Алгоритам за сортирање - 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]

Алгоритмите се многу општа тема. Тоа е посебна наука. За алгоритми би требало да се направи цел форум, а не само тема Мислам дека е подобро да се постираат директни линкови до местата на интернет каде што се објаснети алгоритмите, а и линкови до книги кои ги објаснуваат сите најчесто користени и најдобри алгоритми од сите подобласти на алгоритмите. На пример:
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...
Значи мој предлог, тема каде што ќе се ставаат линкови до објаснувања на алгоритми (ги има многу на интернет) плус линкови од книги. А плус ова да биде и место каде што ќе има дискусија околу алгоритмите, нивна анализа, ако има нешто нејасно и слично.
Поздрав

 

[maximilian]

@loverboy

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

 

[Blagojce]

Баш сега го учиме тоа на fax и за овој алгоритам од maximilian мислам дека би изгледал вака:


Мене потешко ми оди со алгоритмиве бидејќи до сега немам решавано ниеден, а сега браво за maximiian што ја отвори темава ќе може да размениме искуства.

 

[maximilian]

Алгоритам за НЗД - алгоритамот на Евклид

Сега ќе го објаснам алгоритамот на Евклид за наоѓање на НЗД. Овој 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]

Гледам Благојче постирал блок дијаграм, па доколкиа некои што не знаат а ги интересира еве мало објаснување за овие дијаграми.

 

[TataMata]

Maximilian малку направи го поопшт алгоритамот за НЗД, т.е. не за 2 броеви него да наоѓа НЗД за n броеви.

 

[спиро_дт]

пресметување на престапна година :

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]

Maximilian малку направи го поопшт алгоритамот за НЗД, т.е. не за 2 броеви него да наоѓа НЗД за n броеви.

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

 

[vasildb]

пресметување на престапна година :

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 туку со %.

 

[спиро_дт]

oooo da be so 4 bese ... a za % moze i taka a moze i so include math.h

anyway updated

 

[vasildb]

Заборавив, и споредба со два знаци за еднакво се прави "==".

Значи

#include stdio.h

void prestapna();

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

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

 

[fuUuUzZzZy]

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


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

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

Земаме еден четирицифрен природен број 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

____________________________________________

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

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

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

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.

 

[спиро_дт]

Заборавив, и споредба со два знаци за еднакво се прави "==".

Значи

#include stdio.h

void prestapna();

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

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

хехе добро оптимизирано .. бтв го пишував постот без компајлер а у ц/ц++ не сум програмирал одамна па имам забраено некои работи

 

[maximilian]

Maximilian малку направи го поопшт алгоритамот за НЗД, т.е. не за 2 броеви него да наоѓа НЗД за n броеви.

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

 

[maximilian]

Иначе, спиро_дт, алгоритамот за престапна година ти е погрешен. За да биде една година престапна, не е единствен услов таа да биде делива со 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]

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

Нема да е баш ефикасно, мислам дека ќе се согласиш.

 

[dime]

Алгоритам за сортирање - 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.

 

[maximilian]

Нема да е баш ефикасно, мислам дека ќе се согласиш.

Не, токму напротив. Алгоритамот е солиден според мене. Затоа што за него се потребни 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:

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