الگوریتمهای برنامه نویسی از ساده به پیشرفته

[moam]

الگوریتم ضرب ماتریسها

کد:

void matrixmult (int n
                          const number  A [ ] [ ],
                          const number  B [ ] [ ],
                                    number  C [ ] [ ],
{
     index i , j, k;
     for  ( i = 1; I <= n ; i++)
            for (i = 1; j <= n ; j++)}
                    C [i] [j] = 0;
for (k = 1 ; k <= n ; k++)                             C [i][j] = C[i] [j] + A [i][k] * B [k][j]             }}

[moam]

الگوریتم ماتریس استراسن

کد:

void starssen ( int n
                          n × n _ matrix A,
                          n × n _ matrix B,
                          n × n _ matrix & C)
  {
     if ( n <= threshold)
         compute C = A × B using the standard algorithm;
else  {
              partition  A into  four  submatrics A11, A12 , A21,A22;
              partition  B into  four  submatrics B11, B12 , B21,B22;
              compute C = A × B using Starssen’s Method;
          }
     }

[moam]

ضرب اعداد صحیح بزرگ

کد:

large_integer prod2 (large_integer u , large_ integer v)
  {
   large_integer x , y , w , z , r , p , q;
   int n , m;
   n = maximum (number of digits in u,number of digits in v);
   if  (u = = 0 || v = = 0)
           return 0 ;
   else if    (n < = threshold)
         return   u ×  v obtained in the  usual way;        
else {
           m = Į n / 2 ⌡;
              x = u divide  10 ^ m  ;  y = rem 10 ^ m;
              w = v divide  10 ^ m  ;  z = rem 10 ^ m;
               r =  prod2 (x + y, w + z );
               p = prod2 ( x , w )
               q = prod2 ( y , z );
               return  p ×10 ^ 2m + ( r – p – q ) × 10 ^ m +q ;                  }
      }

[moam]

الگوریتم پریم

کد:

void prim ( int n,
                    const number W[ ] [ ],
                    set_ of_edges & F )
       {
              index i , vnear;
              number  min;
              edge  e;
              index   nearest [2..n];
          number distance [2..n];
          F = Ø ;
          for ( i = 2 ; i ≤ n ; i ++) {
                    narest [i] = 1 ;
                    distance [i] = W [1] [i] ;
           }
           repeat ( n-1 times )  {
                min = ∞ ;
                 for ( i = 2 ; i < = n ; i ++)
                       if ( 0 ≤ distance [i] < min )  {
min = distance [i] ;
                vnear = i ;
             }
        e = edge connecting vertices indexed by                     near and  nearest [ vnear ] ;
         add e to F ;
         distance [ vnear ]  = -1 ;
         for ( i = 2 ; i ≤ n ; i ++)  
if ( W[i] [ vnear ] < distance [i])  {
                     distance [i] = W [i] [ vnear ] ;
                     nearest [i] = vnear ;
                   }
              }
      }

[moam]

کد:

void  floyd ( int  n
                      const  number W [][],
                                 number D  [][],
     {  
           index  i , j , k ;
           D  = W ;
           for ( k = 1 ; k ≤ n ; k ++)
                 for ( i = 1; i ≤ n ; i++)
                      for ( j = 1 ; j ≤ n ; j ++)
                           D [i] [j] = minimum ( D [i][j], D[i][k] + D[k][j]);
      }

[moam]

کد:

void kruskal ( int n , int m,
set _ of _ edges E,
set _ of _edges & F )
{
index i , j ;
set _pointer p , q;
edge e ;
sort the m edges in E by weight in
nondecreasing order;
F = Ø ;
intitial (n) ;
while( number of edges in F is less than n-1){
e = edge with least weight not yet
considered ;
i , j = indices of vertices connected by e;
p = find (i) ;
q = find (i) ;
if (! equal ( p, q )) {
merge ( p , q ) ;
add e to F ;
}
}
}

[moam]

الگوریتم دیکسترا

کد:

void dijkstra ( int n,
                       const number W[ ] [ ],
                       set _ of _ edges & F)
      {
            index i , vnear,
            edge e ;
            index touch [2..n];
            number length[2..n];
F = Ø ;
        for ( i = 2; i ≤  n ; i ++ )  {
                   touch [i] = 1 ;
                   length [i]  = W [1][i];
          }
          
          repeat ( n – 1 times ) {
                min = ∞ ;
                for ( i = 2 ; i ≤ n ; i ++)
                     if ( 0 <= length [i] < min )  {
                            min = length [i] ;
vnear = i ;
        }
     e = edge from vertix indexed by touch [vnear]
           to vertex indexed by vnear;
     add e to F;
     for ( i = 2 ; i ≤ n; i ++)

          if ( length [vnear] + W [vnear] [i] < length[i]) {

                length [i] = length [vnear] + W [vnear] [i];
touch [i] = vnear ;
         }
       length [vnear]  = -1;
      }
    }

[zerda]

این الگوریتم ضرب یا multهست که با استفاده از روش DANDCحل شده.و ضرب دو عدد n بیتی رو بیان می کنه.

کد php:

int mult (int x,int y, int n)
{
int s;
int m1,m2,m3;
int A,B,C,D;
S=sign(x)*sign(y);
x=ABS(x);y=ABS(y);
if(n==1){
if(x==1)&&(y==1)
return(S);
else
return(0);
}
else
{
A=left(x,n/2);
B=reght(x,n/2);
C=left(y,n/2);
D=right(y,n/2);
m1=mult(A,c,n/2);
m2=mult(A-B,D-C,n/2);
m3=mult(B,D,n/2);
return(S*leftshift(m1,n)+leftshift(m1+m2+m3,n/2)+m3));
}
} 


الگوریتم ساین،علامت یک عدد رو محاسبه می کنه.تابعABSقدر مطلق یک عدد رو بر می کردونه.توابع لفت و رایت به ترتیب به تعداد تعیین شده ،بیتهای سمت چپ و راست رو جدا می کنند.توابع leftshiftو rightshift به ترتیب به تعداد بیتهای تعیین شده عمل شیفت به چپ و شیفت به راست رو انجام می دهند.

سلام من میخواستم بدونم این برنامه همون برنامه ضرب دو عدد n بیتی است یا فرق داره با تشکر.

[اشک]

سلام من میخواستم بدونم این برنامه همون برنامه ضرب دو عدد n بیتی است یا فرق داره با تشکر.

متأسفم که دیر به پستتون جواب دادم.دوتا برنامه مشابه ،ممکنه ازنظر سورس متفاوت باشن اما یک خروجی و جواب ازشون انتظار میره.راههای رسیدن به هدف متفاوتن.اما موضوع اینجاست که من تو ذهن شما نیستم تا برنامه ی مد نظرتونو با این الگوریتم مقایسه کنم و دقیق جوابتونو بدم.

[اشک]

جستجوی اول عمقی یا depth_first search

کد php:

for each vertex u ∈ v[G]
white→do color [U]
null →M[u]
0→time
for each vertex U∈ V[G]
do if color [U]=white
then DFS-VISIT(U) 


که DFS-VISIT :

کد php:

gray→color[U]
time+1→time
time→d[U]
for each V ∈ adj [U]
do if color [V]=white
then U→M[V]
DFS-VISIT(V)
black→color[U]
time+1→time→f[U] 


که در این دو الگوریتم M پدر هر رأس.d کوتاهترین مسیر از ریشه تا رأس مورد نظر است.