ايران ويج

صفحه‌ها: 1 2 3

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

کد: 
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]             }}

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

کد: 
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;

          }

     }

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

کد: 
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 ;                  }

      }

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

کد: 
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 ;

                   }

              }

      }

کد: 
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]);

      }

کد: 
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 ;

 }

 } 

 }

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

کد: 
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;

      }

    }

(۱۳-اسفند-۱۳۸۸, ۰۰:۴۲:۲۱)اشک نوشته است: [ -> ]این الگوریتم ضرب یا 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 کوتاهترین مسیر از ریشه تا رأس مورد نظر است.

صفحه‌ها: 1 2 3

moam

moam

moam

moam

moam

moam

moam

zerda

اشک

اشک