رتبه 1 کنکور کارشناسی ارشد

صفحه: [1]   پایین
  چاپ صفحه  
نويسنده موضوع: الگوريتم ترانهاده ماتريس اسپارس  (دفعات بازدید: 5183 بار)
Yas
کاربر جدید
*

تشكرها : 7
آفلاین آفلاین

تعداد ارسال: 40



ديدن مشخصات
« : 15 مرداد 1389,ساعت 16:00:50 »

لطفا الگوريتم ترانهاده ماتريس اسپارس رو برام بنويسيد ؟ خجالت کشیدن
« آخرين ويرايش: 15 مرداد 1389,ساعت 16:24:00 توسط تقدسی » خارج شده است

يا رب نظر تو برنگردد    برگشتن روزگار سهل است
تقدسی
Super Manager
*

تشكرها : 100
آفلاین آفلاین

جنسيت : دختر
تعداد ارسال: 380

هیهات من الذله ...


ديدن مشخصات WWW
« پاسخ #1 : 15 مرداد 1389,ساعت 16:13:24 »

با سلام

کد:
/* _MATRIX_H */


#ifndef _MATRIX_H
#define _MATRIX_H

#include <cstdlib>
#include <map>
#include <vector>

template <class T>
class Matrix
{
public:
    typedef std::map<size_t, std::map<size_t , T> > mat_t;
    typedef typename mat_t::iterator row_iter;
    typedef std::map<size_t, T> col_t;
    typedef typename col_t::iterator col_iter;

    Matrix(size_t i){ m=i; n=i; }
    Matrix(size_t i, size_t j){ m=i; n=j; }

    inline
    T& operator()(size_t i, size_t j)
    {
        if(i>=m || j>=n) throw;
        return mat[i][j];
    }
    inline
    T operator()(size_t i, size_t j) const
    {
        if(i>=m || j>=n) throw;
        return mat[i][j];
    }

    std::vector<T> operator*(const std::vector<T>& x)
    {  //Computes y=A*x
        if(this->m != x.size()) throw;

        std::vector<T> y(this->m);
        T sum;

        row_iter ii;
        col_iter jj;

        for(ii=this->mat.begin(); ii!=this->mat.end(); ii++){
            sum=0;
            for(jj=(*ii).second.begin(); jj!=(*ii).second.end(); jj++){
                sum += (*jj).second * x[(*jj).first];
            }
            y[(*ii).first]=sum;
        }

        return y;
    }

    void printMat()
    {
        row_iter ii;
        col_iter jj;
        for(ii=this->mat.begin(); ii!=this->mat.end(); ii++){
            for( jj=(*ii).second.begin(); jj!=(*ii).second.end(); jj++){
                std::cout << (*ii).first << ' ';
                std::cout << (*jj).first << ' ';
                std::cout << (*jj).second << std::endl;
            }
        } std::cout << std::endl;
    }
    
protected:
    Matrix(){}

private:
    mat_t mat;
    size_t m;
    size_t n;
};

#endif


و  قسمت  main &program test

کد:
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <cmath>
#include <time.h>
#include "Matrix.h"

using namespace std;

int init(Matrix<long double> &A)
{
    ifstream fin("matin.txt");
    int n,length,i,j;
    if(fin.is_open())
    {
        fin >> n;
fin >> length;
        int k=0;
        while(k<length){ fin >> i >> j; fin >> A(i-1,j-1); k++; }
        fin.close();
    }
    else return 0;
    return n;
}

int main()
{
    Matrix<long double> A(1806);
    vector<long double> x(1806,1), y;
    long double sum;
    int n,k=0;
    clock_t t0,tf;
    cout.precision(17);

    n=init(A);
    
    //timed multiplication
    t0=clock();
    for(int i=0;i<1000;i++){ y=A*x; }
    tf=clock()-t0;
    
    //output last element
    cout << y[1805]
    //output time to multiply
    cout << "\n\n" << (double)tf/((double)(CLOCKS_PER_SEC)*(1000.0));

    //do naive multiply for last row to check last element of y
    long double tmp=0;
    for(int i=0;i<1806;i++) tmp+=A(1805,i);
    cout << "\n" << tmp <<"\n";

    return 0;
}
خارج شده است

كاربران گرامی : لطفاً قبل از هرگونه فعاليت ابتدا قوانين انجمن را مطالعه  و قبل از ارسال جديد در انجمن جستجو نماييد.
تقدسی
Super Manager
*

تشكرها : 100
آفلاین آفلاین

جنسيت : دختر
تعداد ارسال: 380

هیهات من الذله ...


ديدن مشخصات WWW
« پاسخ #2 : 15 مرداد 1389,ساعت 16:28:59 »

در کد زیر مراحل ذکر شده در پایین به ترتیب انجام می شود:

۱ : خواندن ماتریس اسپارس و چاپ آن
۲ : چاپ ماتریس واقعی
۳ : جمع و تفریق و ضرب با ماتریسی دیگر

کد:
#include<conio.h>
#include<iostream.h>
#define Max 30
/*********************************************************/
class string;
class Sparse;
/*********************************************************/
class SparseNode
{
 int row, col;
 float value;
 friend class Sparse;
};
/*********************************************************/
class Sparse
{
  int Row, Col, Terms;
  SparseNode Data[Max];
 public:
  void ReadSparse( void );
  void WriteSparse( void );
  void WriteMatrix( void );
  void AddSparse( Sparse a, Sparse b );
  void ManfiSparse();
  void FastTranspose( Sparse b );
  int StoreSum( int sum, int&LastInResult, int r, int c );
  void Sparse :: MulSparse( Sparse a, Sparse b );
};
/*********************************************************/
void Sparse :: ReadSparse( void )
{
 clrscr();
 int i = 0;
 cout << "\n\n@ Lotfan Ettelaat Zir Ra Dar Mored Matrise Sparse Vared Konid : \n\n"
    << "$ Tadade Satrha              : ";
 cin >> Row;
 cout << "$ Tedade Sotoonha            : ";
 cin >> Col;
 do
 {
  cout << "$ Tedade Anasore Gheyre Sefr : ";
  cin >> Terms;
  if( Terms > ( Row * Col ) || Terms < 0 )
   cerr << "\nERROR ! ( In Tedad Ghabele Ghabool Nemibashad )\n\n";
 }
 while( Terms > ( Row * Col ) || Terms < 0 );
 while( i < Terms )
 {
  cout << "\n# Lotfan Shomarehye Satr Va Sotoone Onsore "
     << ( i + 1 )
     << " -om Ra Vared Konid : ";
  cin >> Data[i].row
    >> Data[i].col;
  if( Data[i].row > Row || Data[i].col > Col || Data[i].row < 1 || Data[i].col < 1 )
   cerr << "\nERROR ! ( In Jayegah Dar Moshakhkhasat Matris Nemigonjad )\n";
  else
  {
   cout << "* Lotfan Meghdar Onsor Ra Vared Konid : ";
   cin >> Data[i].value;
   i++;
  }
 }
 clrscr();
}
/*********************************************************/
void Sparse :: WriteSparse( void )
{
 int i;
 cout << "\n\n# Moshakhkhasat Matris Be Soorate Zir Ast :"
    << "\n\n~ Tedade Satrha = "
    << Row
    << "\n~ Tedade Sotoonha = "
    << Col
    << "\n~ Tedade Anasore Gheyre Sefr = "
    << Terms
    << "\n\n~ Liste Anasor Gheyre Sefre Matris Be Sharhe Zir Ast :\n\n"
    << "Satr\tSotoon\tMeghdar\n";
 for( i = 0; i < Terms; i++ )
  cout << Data[i].row
     << "\t"
     << Data[i].col
     << "\t"
     << Data[i].value
     << endl;
 getch();
}
/*********************************************************/
void Sparse :: WriteMatrix( void )
{
 clrscr();
 int i, j;
 float Matrix[Max][Max] = {0};
 cout << "\n\nMatrix Vaghei :\n\n";
 for( i = 0; i < Terms; i++ )
  Matrix[Data[i].row-1][Data[i].col-1] = Data[i].value;
   for( i = 0; i <= Col; i++ )
  cout << "[" << ( i ) << "]\t";
 for( i = 0; i < Row; i++ )
 {
  cout << "\n\n"
     << "[" << ( i+1 ) << "]";
  for( j = 0; j < Col; j++ )
  {
   cout << "\t"
      << Matrix[i][j];
  }
 }
 getch();
   clrscr();
}
/*********************************************************/
void Sparse :: AddSparse( Sparse a, Sparse b )
{
 int i, j, k;
 i = j = k = 0;
 if( a.Row != b.Row || a.Col != b.Col )
 {
  cout << "\n*** ERROR !!! Nemitavan In 2 Matris Ra Ba Ham Jame Kard ***";
  return;
 }
 Row = a.Row;
 Col = a.Col;
 while( i < a.Terms && j < b.Terms )
 {
  if( a.Data[i].row < b.Data[j].row || ( a.Data[i].row == b.Data[j].row && a.Data[i].col < b.Data[j].col ) )
  {
   Data[k].row = a.Data[i].row;
   Data[k].col = a.Data[i].col;
   Data[k++].value = a.Data[i++].value;
  }
  else if( a.Data[i].row > b.Data[j].row || ( a.Data[i].row == b.Data[j].row && a.Data[i].col > b.Data[j].col ) )
  {
   Data[k].row = b.Data[j].row;
   Data[k].col = b.Data[j].col;
   Data[k++].value = b.Data[j++].value;
  }
  else if( a.Data[i].value + b.Data[j].value )
  {
   Data[k].row = a.Data[i].row;
   Data[k].col = a.Data[i].col;
   Data[k++].value = a.Data[i++].value + b.Data[j++].value;
  }
  else
  {
   i++;
   j++;
  }
 }
 while( i < a.Terms )
 {
  Data[k].row = a.Data[i].row;
  Data[k].col = a.Data[i].col;
  Data[k++].value = a.Data[i++].value;
 }
 while( j < b.Terms )
 {
  Data[k].row = b.Data[j].row;
  Data[k].col = b.Data[j].col;
  Data[k++].value = b.Data[j++].value;
 }
 Terms = k;
}
/*********************************************************/
void Sparse :: ManfiSparse()
{
 for( int i = 0; i < Terms; i++ )
  Data[i].value *= -1;
}
/*********************************************************/
void Sparse :: FastTranspose( Sparse a )
{
 int i, k;
 int RowSize[Max], RowStart[Max];
 Row = a.Col;
 Col = a.Row;
 Terms = a.Terms;
 for( i = 0; i < a.Col; i++ )
    RowSize[i] = 0;
 for( i = 0; i < a.Terms; i++ )
  RowSize[a.Data[i].col-1]++;
 RowStart[0] = 0;
 for( i = 1; i < a.Col; i++ )
  RowStart[i] = RowStart[i-1] + RowSize[i-1];
 for( i = 0; i < a.Terms; i++ )
 {
  k = RowStart[a.Data[i].col-1]++;
  Data[k].row = a.Data[i].col;            
  Data[k].col = a.Data[i].row;
  Data[k].value = a.Data[i].value;
 }
}
/*********************************************************/
int Sparse :: StoreSum( int sum, int&LastInResult, int r, int c )
{
 if( sum != 0 )
  if( LastInResult < Max-1 )
  {
   LastInResult++;
   Data[LastInResult].row = r;
   Data[LastInResult].col = c;
   Data[LastInResult].value = sum;
   return 0;
  }
  else
  {
   cerr << "\n*** ERROR !!! Tedade Anasore Gheyre Sefr Az Fazaye Arayeh Biroon Mizanad ***\n";
   return 1;
  }
 else
  return 0;
}
/*********************************************************/
char compare( int x, int y )
{
 if( x < y )
  return '<';
 else if( x == y )
  return '=';
 return '>';
}
/*********************************************************/
void Sparse :: MulSparse( Sparse a, Sparse b )
{
 if( a.Col != b.Row )
 {
  cout << "\n*** ERROR !!! Zarbe 2 Matris Emkan Pazir Nist ***";
  Row = 0;
  Col = 0;
  Terms = 0;
  return;
 }
 if( ( a.Terms == Max ) || ( b.Terms == Max ) )
 {
  cout << "*** ERROR !!! Yek Fazaye Khali Dar Matris 'A' Ya 'B' Lazem Ast ***";
  Row = 0;
  Col = 0;
  Terms = 0;
  return;
 }
 Sparse d;
 d.FastTranspose( b );
 int currRowIndex = 0, LastInResult = -1, currRowBegin = 0, currRowA = a.Data[0].row;
 a.Data[a.Terms].row = a.Row;
 d.Data[b.Terms].row = b.Col;
 d.Data[b.Terms].col = -1;
 int sum = 0;
 while( currRowIndex < a.Terms )
 {
  int currColB = d.Data[0].row;
  int currColIndex = 0;
  while( currColIndex <= b.Terms )
  {
   if( a.Data[currRowIndex].row != currRowA )
   {
    if( StoreSum( sum, LastInResult, currRowA, currColB ) )
    {
     Row = 0;
     Col = 0;
     Terms = 0;
     cout << "\n *** ERROR !!! ***";
     return;
    }
    else
     sum = 0;
    currRowIndex = currRowBegin;
    while ( d.Data[currColIndex].row == currColB )
     currColIndex++;
    currColB = d.Data[currColIndex].row;
   }
   else if( d.Data[currColIndex].row != currColB)
   {
    if( StoreSum( sum, LastInResult, currRowA, currColB ) )
    {
     Row = 0;
     Col = 0;
     Terms = 0;
     cout << "\n *** ERROR !!! ***";
     return;
    }
    else
     sum = 0;
    currRowIndex = currRowBegin;
    currColB = d.Data[currColIndex].row;
   }
   else switch( compare( a.Data[currRowIndex].col, d.Data[currColIndex].col ) )
   {
    case '<' :
     currRowIndex++;
     break;
    case '=' :
     sum += a.Data[currRowIndex].value * d.Data[currColIndex].value;
     currRowIndex++;
     currColIndex++;
     break;
    case '>' :
     currColIndex++;
   }
  }
  while( a.Data[currRowIndex].row == currRowA )
   currRowIndex++;
  currRowBegin = currRowIndex;
  currRowA = a.Data[currRowIndex].row;
 }
 Row = a.Row;
 Col = b.Col;
 
Terms = LastInResult + 1;
}/*********************************************************/
void Meno( void )
{
 clrscr();
 cout << "\n# Lotfan Alamat Morede Nazar Ra Vared Konid :\n"
    << "\n+ : Jam Ba Matrisi Digar"
    << "\n- : Tafrigh Az Matrisi Digar"
    << "\n* : Zarb Dar Matrisi Digar"
    << "\nP : Chape Matrise Vagheyi"
    << "\nT : Tarane Hadeye Matris";
}
/*********************************************************/
void main( void )
{
 Moarrefi();
 Sparse a, b, c;
 a.ReadSparse();
 a.WriteSparse();
 Meno();
 switch( getch() )
 {
  case '+' :
   b.ReadSparse();
   b.WriteSparse();
   c.AddSparse(a,b);
         cout << "\n\nAnswer Is : ";
   c.WriteSparse();
   break;
  case '-' :
       b.ReadSparse();
   b.WriteSparse();
   b.ManfiSparse();
   c.AddSparse(a,b);
         cout << "\n\nAnswer Is : ";
   c.WriteSparse();
   break;
  case '*' :
       b.ReadSparse();
   b.WriteSparse();
   c.MulSparse(a,b);
         clrscr();
   cout << "\n\nAnswer Is : ";
   c.WriteSparse();
   break;
  case 'p' :
   a.WriteMatrix();
   break;
  case 't' :
   c.FastTranspose( a );
         clrscr();
         cout << "\n\nAnswer Is : ";
   c.WriteSparse();
       break;
 }
}
« آخرين ويرايش: 16 مرداد 1389,ساعت 21:25:47 توسط تقدسی » خارج شده است

كاربران گرامی : لطفاً قبل از هرگونه فعاليت ابتدا قوانين انجمن را مطالعه  و قبل از ارسال جديد در انجمن جستجو نماييد.
انجمن تخصصی استادان و دانشجویان کامپیوتر ایران
« پاسخ #2 : 15 مرداد 1389,ساعت 16:28:59 »

شما هم صاحب یک سامانه پیام کوتاه با شماره اختصاصی شوید!
 خارج شده است
Yas
کاربر جدید
*

تشكرها : 7
آفلاین آفلاین

تعداد ارسال: 40



ديدن مشخصات
« پاسخ #3 : 16 مرداد 1389,ساعت 16:43:24 »

سلام راستش من از اين كدهايي كه نوشتيد چيزي متوجه نشدم اگه ميشه به راه ساده تري برام بنويسيد . در ضمن خواهشا به زبان C++ بنويسيد كه اجرا بشه . مرسي از كمكتون .
خارج شده است

يا رب نظر تو برنگردد    برگشتن روزگار سهل است
تقدسی
Super Manager
*

تشكرها : 100
آفلاین آفلاین

جنسيت : دختر
تعداد ارسال: 380

هیهات من الذله ...


ديدن مشخصات WWW
« پاسخ #4 : 16 مرداد 1389,ساعت 17:36:30 »

با سلام
این برنامه به زبان c++  هست.کد اولی خیلی راحت بیان شده.تا قبل از اینکه عملبات جمع و غیره انجام شود،مربوط به ماتریس اسپارس هست.با دقت بخوانید.انشالله متوجه خواهید شد.بازم اگه متوجه نشدید سوال کنید.اما دستورات سی پلاس پلاس میباشد.
خارج شده است

كاربران گرامی : لطفاً قبل از هرگونه فعاليت ابتدا قوانين انجمن را مطالعه  و قبل از ارسال جديد در انجمن جستجو نماييد.
Yas
کاربر جدید
*

تشكرها : 7
آفلاین آفلاین

تعداد ارسال: 40



ديدن مشخصات
« پاسخ #5 : 16 مرداد 1389,ساعت 20:40:17 »

از شما ممنونم من به جواب شما اعتماد دارم ولي من تازه برنامه نويسي مي خونم و اين برنامه خيلي طولاني اگه ميشه اگه امكانش هست فقط  الگوريت قسمت ترانهاده ماتريس اسپارس و برام بنويسيد . ممنون و متشكر از لطف شما.


 :-\سلام . راه ساده تري پيدا نشد در مورد سوال بالا ؟


*_ ارسال های پیاپی یکی شدند.
« آخرين ويرايش: 18 مرداد 1389,ساعت 17:30:13 توسط كیانی » خارج شده است

يا رب نظر تو برنگردد    برگشتن روزگار سهل است
تقدسی
Super Manager
*

تشكرها : 100
آفلاین آفلاین

جنسيت : دختر
تعداد ارسال: 380

هیهات من الذله ...


ديدن مشخصات WWW
« پاسخ #6 : 18 مرداد 1389,ساعت 14:21:23 »

با سلام
کاربر محترم به توضیحات زیر توجه کنید:
ابندا کلاس ماتریس در نظر گرفته میشود:
کد:
class Sparse
{
  int Row, Col, Terms;
  SparseNode Data[Max];
 public:
  void ReadSparse( void );
  void WriteSparse( void );
  {

در کلاس بالا مراحل زیر به ترتیب انجام میشود:
1.خواندن ماتریس اسپارس و چاپ آن


حال توابع مورد بررسی قرار میگیرند.

در تایع زیر عمل خواندن صورت میگیرد:

کد:
void Sparse :: ReadSparse( void )
{
 clrscr();
 int i = 0;
 cout << "\n\n@ Lotfan Ettelaat Zir Ra Dar Mored Matrise Sparse Vared Konid : \n\n"
    << "$ Tadade Satrha              : ";
 cin >> Row;
 cout << "$ Tedade Sotoonha            : ";
 cin >> Col;
 do
 {
  cout << "$ Tedade Anasore Gheyre Sefr : ";

  cin >> Terms;
  if( Terms > ( Row * Col ) || Terms < 0 )
   cerr << "\nERROR ! ( In Tedad Ghabele Ghabool Nemibashad )\n\n";
 }
 while( Terms > ( Row * Col ) || Terms < 0 );
 while( i < Terms )
 {
  cout << "\n# Lotfan Shomarehye Satr Va Sotoone Onsore "
     << ( i + 1 )
     << " -om Ra Vared Konid : ";
  cin >> Data[i].row
    >> Data[i].col;
  if( Data[i].row > Row || Data[i].col > Col || Data[i].row < 1 || Data[i].col < 1 )
   cerr << "\nERROR ! ( In Jayegah Dar Moshakhkhasat Matris Nemigonjad )\n";
  else
  {
   cout << "* Lotfan Meghdar Onsor Ra Vared Konid : ";
   cin >> Data[i].value;
   i++;
  }
 }
 clrscr();
}

تابع چاپ ماتریس اسپارس:
کد:
void Sparse :: WriteSparse( void )
{
 int i;
 cout << "\n\n# Moshakhkhasat Matris Be Soorate Zir Ast :"
    << "\n\n~ Tedade Satrha = "
    << Row
    << "\n~ Tedade Sotoonha = "
    << Col
    << "\n~ Tedade Anasore Gheyre Sefr = "
    << Terms
    << "\n\n~ Liste Anasor Gheyre Sefre Matris Be Sharhe Zir Ast :\n\n"
    << "Satr\tSotoon\tMeghdar\n";
 for( i = 0; i < Terms; i++ )
  cout << Data[i].row
     << "\t"
     << Data[i].col
     << "\t"
     << Data[i].value
     << endl;
 getch();
}

با توجه به موارد ذکر شده در بالا اکنون قادر خواهید بود قدم به  قدم مراحل را طی کرده و مفاهیم را درک کنید.

تلاش کنید.تلاش کنید.تلاش کنید.
خارج شده است

كاربران گرامی : لطفاً قبل از هرگونه فعاليت ابتدا قوانين انجمن را مطالعه  و قبل از ارسال جديد در انجمن جستجو نماييد.
انجمن تخصصی استادان و دانشجویان کامپیوتر ایران
« پاسخ #6 : 18 مرداد 1389,ساعت 14:21:23 »


رتبه 1 کنکور کارشناسی ارشد

 خارج شده است
Yas
کاربر جدید
*

تشكرها : 7
آفلاین آفلاین

تعداد ارسال: 40



ديدن مشخصات
« پاسخ #7 : 18 مرداد 1389,ساعت 15:44:54 »

خيلي ممنون از راهنماييتون
خارج شده است

يا رب نظر تو برنگردد    برگشتن روزگار سهل است
انجمن تخصصی استادان و دانشجویان کامپیوتر ایران
   


رتبه 1 کنکور کارشناسی ارشد

 خارج شده است
صفحه: [1]   بالا
  چاپ صفحه  
 
پرش به :