22948

МАСИВИ. БАГАТОВИМІРНІ МАСИВИ

Лекция

Информатика, кибернетика и программирование

middle] void merge int min int middle int max {int i j m1m2; i=m1=min; m2=middle1; while m1 =middle m2 =max if a[m1] a[m2] b[i]= a[m1]; else b[i]= a[m2]; while m1 =middle b[i]= a[m1]; while m2 =max b[i]= a[m2]; for i=min; i =max; i a[i]=b[i]; } швидке упорядкованому за зростанням масиву a[] довжини n=2 за допомогую масиву b[] void...

Русский

2013-08-04

131.5 KB

2 чел.

ТЕМА: МАСИВИ. БАГАТОВИМІРНІ МАСИВИ.

Прикл. Пошук компоненти.

Аналіз

Вх: символьний вектор -константа, ,

      

Вих:

Зал:  Нехай . Тоді

Вим: Побудувати Сі – функцію.    

Проект.

 лічильник,

,

Блок-схема……

Прога   

===============================================================================

#include < stdio.h >

 int search(unsigned сhar x,  unsigned сhar c[], int n)

 {int i=0,l;

         

     for (  l=(c[0]==x)? 0: -1; (++i<=n-1 && l==-1); )

             if (c[i]==x) l==i;

    return l;

 }

#define m 100

void main (void)

{int i;  float a[m],x;

 scanf (“%f”, &x);  /* що шукати  */ 

 for ( i=0; (i<n-1);i++ )  scanf (“%f”, &c[i]);  /* читання елементів масиву зі станд. вхідного потоку  */ 

 printf(“\n%d”, search( x,  a, m));

}

/* АХТУНГ:  ПРОГА НА ЖАЛЬ  НЕ ВІДЛАГОДЖУВАЛАСЬ !!!!!!!!!!!!!!!     */

 ===============================================================================

Впр. Відлагодити прогу!

Сем. Багатовимірний масив – це масив(=вектор), компонентами якого є  масиви(=ветори)  певного фіксованого типу. Нпр., масив-матриця matr={{1.0, 2.0, 3.0, 4.0, 5.0}, {1.0, 2.0, 3.0, 0.0, 5.0} } має  два (=довжина масиву) рядки - одновимірні-масиви довжини  5. В памяті вони розташуваються підряд в такій саме послідовності. Спочатку елементи першого рядка, безпосередньо за ними – другого.

Синт. Опис даного масиву має вигляд:  double matr[2][5]; .  Обробка здійснюється за допомогою функції індексування. При цьому можливе      подвійне індексування.  Тому що значенням matr[i] є масив і його можна в свою чергу індексувати і отримувати доступ до компонентів рядків матриці.   

Нпр.  matr[0]={1.0, 2.0, 3.0, 4.0, 5.0},  matr[1]={1.0, 2.0, 3.0, 0.0, 5.0}.

        matr[0][0]=1.0, matr[1][4]=5.0.

Взагалі,  змінній matr[i][j]  (, )  відповідає адреса   matr[0][0](=matr)+ i*розмір-рядка(=sizeof(double)*5) +j* sizeof(double)/

УВАГА!!! Якщо двовимірний масив передається  функції у якості аргумента, то відповідний формальний параметр повинен містити фіксовану кількість стовпчиків(=довжину вектора-рядка матриці), яка обов’язково має бути присутня в оголошенні типу параметра. 

Нпр.,   для масиву matr заголовок функції  міг би мати вигляд  void func(double _matr[2][5],…) або void func(double _matr[][5], int n,….), де  

показує кількість рядків  матриці у конкретному виклику функції.

Прикл. Лабораторна  робота 3. У  заданій  числовій матриці порядку  упорядкувати за зростанням всі рядки матриці, що містять  відємний елемент.

Аналіз

Вх: матриця  

Вих: матриця

Зал:  - це матриця  з упорядкованими за зростанням рядками, що містять нульові елементи.

Вим: Побудувати Сі –прогу з функціями: 1)сортування масиву за зростанням, 2) зясування  чи містить  масив  нульовий елемент та

3) обробки матриці (=упорядкування відповідних рядків).

Проект.

/* Бульбашкове  сортування  масиву довжини */

void  bubble (double a[], unsigned int k)

{unsigned int pr,i, temp ;

    do {   pr=0;

           for (i=1;i<k; i++ )

            if (a[i-1]>a[i]) {temp=a[i-1]; a[i-1]=a[i]; a[i]=temp; pr=1;}

          }

   while (pr)

}

/* зясування  чи містить  масив довжини  нульовий елемент */

int search(float x, double c[], unsigned int n)

 {…… }

/* обробки матриці порядку (=упорядкування за зростанням рядків, що містять 0) */

void matr_processing( double c[][m], unsigned int k)

 {int i;

         

     for ( i=0; (i<n;i++ )

             if (search(0.0,  c[i], m)) bubble(c[i],m);

  }

Блок-схема……

Прога

===============================================================================

#include < stdio.h >

/* Бульбашкове  сортування  масиву довжини */

        void bubble (double a[], unsigned int k)

         {……}

/* зясування  чи містить  масив довжини  нульовий елемент */

int search(double  x, double c[], unsigned int n)

 {…… }

/* обробки матриці порядку (=упорядкування за зростанням рядків, що містять 0) */

void matr_processing( double c[][m], unsigned int k)

 {…..   }

/* виведення масиву довжини */

void write_array( double a[], unsigned int k)

 { int i;  

    printf(“\n”);

           for ( i=0; (i<k-1);i++ )  printf(“%3.1f\t”, a[i]);

        }

#define m 5

#define n  4

void main (void)

{ int i;  

  double cc[n][m]={{1.0, 2.0, 3.0, 4.0, 5.0},

                             {1.0, 2.0, 3.0, 0.0, 5.0},

                             {1.0, 2.0, 0.0, 4.0, 5.0},

                             {0.0, 2.0, 3.0, 4.0, 5.0}

                            };

 

 matr_processing(  cc, n);

 for ( i=0; (i<n-1);i++ )  write_array( cc[i], m);  /* виведення го рядка матриці  */ 

}

/* АХТУНГ!   ПРОГА НА ЖАЛЬ  НЕ ВІДЛАГОДЖУВАЛАСЬ…..      */

    ===============================================================================

  Впр. 1) Відлагодити прогу!  На екран має бути видана матриця:

                                                                                                                  1.0, 2.0, 3.0, 4.0, 5.0

                                                                                           0.0, 1.0, 2.0, 3.0, 5.0

                                                                                           0.0  1.0, 2.0, 4.0, 5.0

                                                                                           0.0, 2.0, 3.0, 4.0, 5.0

                      2) Передбачити в прозі  введення елементів матриці   сс   зі вхідного потоку.  

Прикл. Бінарний пошук компоненти в масиві.

Аналіз

Вх: цілий  вектор -константа, ,

      

Вих:

Зал:  Нехай . Тоді , .

Вим: Побудувати Сі – функцію.    

Проект……….

Блок-схема……

Прога   

/*  Бінарний пошук компоненти  x  в упорядкованому за зростанням масиві  c[]  довжини  n */

#include < stdio.h >

 int binsearch( int x,  int c[], int n)

 {int low, high, mid;

             low=0;  high=n-1;

      while (low <= high )

             { mid=(low+high)/2;

                 if (x<c[mid]) high= mid-1;

                     else if (x>c[mid]) low=mid+1;

                                else /*  компоненту  знайдено */

                                              return mid;

              
                    }
/*  компоненту не знайдено */

    return -1;

 }

#define m 100

void main (void)

{int i;  float a[m],x;

 scanf (“%f”, &x);  /* що шукати  */ 

 for ( i=0; (i<n-1);i++ )  scanf (“%f”, &c[i]);  /* читання елементів масиву зі станд. вхідного потоку  */ 

 printf(“\n%d”, binsearch( x,  a, m));

}

/* АХТУНГ:  ПРОГА  НЕ ВІДЛАГОДЖУВАЛАСЬ !     */

Впр. Відлагодити  прогу !

Прикл. «Швидке» сортування масиву. Алгоритм злиття  (Дж. Фон Нойман).

Аналіз

Вх: цілий  вектор -константа, ,

Вих:  цiлий вектор .

Зал:   є  упорядкованим за зростанням  вектором .

Вим: Алгоритм має здійснювати не більше ] порівнянь та переміщень елементів масиву. Побудувати Сі – функцію.    

Проект……….

Блок-схема……

Прога   

#include < stdio.h >

#define n 1024

static int a[n], b[n];

/*  «злиття» сусідніх упорядкованих сегментів  а[min..middle]    та   а[middle+1..max] масиву а[]  в

     упорядкований сегмент b[min..max]    массиву b[]  і копіювання його назад в  а[min..middle]    */

void merge( int min,  int middle, int max)

 {int i, j, m1,m2;

             i=m1=min;  m2=middle+1;

      while (m1<=middle &&  m2<=max)

               if (a[m1]<a[m2]) b[i++]= a[m1++];

                     else  b[i++]= a[m2++];

      while (m1<=middle)  b[i++]= a[m1++];

      while (m2<=max)   b[i++]= a[m2++];

      for (i=min; i<=max; i++) a[i]=b[i];               

  }                                                         

/*  «швидке» упорядкованому за зростанням масиву  a[]  довжини  n=2  за допомогую масиву   b[]*/

void sort_merge2( )

 { int min,  middle, max, part=1;

                 while (2*part<=n)

             {   min=0;   middle=part-1,  max=2*part-1;

                  while (min<n) { merge( min,  middle,  max);

                                           min=max+1;

                                           middle=max+part;

                                           max=middle+part;      

                                        }

                  part*=2;

              }

   }

/*  «швидке» упорядкування за зростанням масиву  a[]  довжини  n  за допомогую масиву   b[]*/

void sort_merge( )

 { int min,  middle, max, part=1;

      while (part<=n)

             {   min=0;   middle=part-1; max=2*part-1;

                  if (max > n-1) max=n-1;   

                  while (min<n) { merge( min,  middle,  max);

                                           min=max+1;

                                           middle=max+part; if (middle >= n-1) min=n;   

                                           max=middle+part;  if (max > n-1) max=n-1;   

                                        }

                  part*=2;

              }

   }

                                     

void main (void)

{int i;  

for ( i=0; (i<n-1);i++ )  scanf (“%f”, &a[i]);  /* читання елементів масиву зі станд. вхідного потоку  */ 

 sort_merge( );

 for ( i=0; (i<n-1);i++ ) printf(“\n%d”, a[i]);

 /* читання елементів масиву зі станд. вхідного потоку  */  

}

/* АХТУНГ:  ПРОГА  НЕ ВІДЛАГОДЖУВАЛАСЬ !     */

Впр. 1) Відлагодити  прогу !

       2) Зробити масив  a[] та довжину n  вхідними параметрами  функцій sort_merge2   та  sort_merge.

       3) Відмовитись в  функції merge від заключного копіювання сегменту b[min..max] в масив a[].


 

А также другие работы, которые могут Вас заинтересовать

17328. ПРЕДМЕТ І ЗАВДАННЯ КУРСУ ПОЛІТЕКОНОМІЇ 85.5 KB
  ПРЕДМЕТ І ЗАВДАННЯ КУРСУ ПОЛІТЕКОНОМІЇ 1. Предмет курсу Економічне життя суспільства є надзвичайно багатогранним. Його вивчає система економічних наук які включають науки про загальні закони економічного розвитку галузеві економічні науки науки що розглядають конкр...
17329. ЕКОНОМІЧНА ДУМКА СТАРОДАВНЬОГО СВІТУ ТА СЕРЕДНЬОВІЧЧЯ. МЕРКАНТИЛІЗМ 263.5 KB
  ЕКОНОМІЧНА ДУМКА СТАРОДАВНЬОГО СВІТУ ТА СЕРЕДНЬОВІЧЧЯ. МЕРКАНТИЛІЗМ Історія економічної думки бере свій початок у глибокій давнині. Уже первісні люди мали якісь зачатки господарських знань котрі були результатом осмислення виробничого досвіду. З розвитком сус
17330. КЛАСИЧНА ШКОЛА ПОЛІТИЧНОЇ ЕКОНОМІЇ 220 KB
  КЛАСИЧНА ШКОЛА ПОЛІТИЧНОЇ ЕКОНОМІЇ Розвиток капіталістичних відносин спричинив занепад меркантилізму передовсім в Англії найбільш економічно розвинутій країні. Інтереси буржуазії переміщуються зі сфери обігу у сферу виробництва. На перший план виходить проми
17331. ЕВОЛЮЦІЯ КЛАСИЧНОЇ ПОЛІТИЧНОЇ ЕКОНОМІЇ В ПЕРШІЙ ПОЛОВИНІ ХІХ СТОЛІТТЯ. ЗАВЕРШЕННЯ КЛАСИЧНОЇ ТРАДИЦІЇ 309 KB
  Еволюція класичної політичної економії в першій половині ХІХ століття. завершення класичної традиції Класична школа політичної економії започаткована Адамом Смітом і Давидом Рікардо справила великий вплив на дальший розвиток економічної науки та формуванн...
17332. КРИТИЧНИЙ НАПРЯМ ПОЛІТИЧНОЇ ЕКОНОМІЇ. ФОРМУВАННЯ СОЦІАЛІСТИЧНИХ ІДЕЙ 97 KB
  КРИТИЧНИЙ НАПРЯМ ПОЛІТИЧНОЇ ЕКОНОМІЇ. ФОРМУВАННЯ СОЦІАЛІСТИЧНИХ ІДЕЙ Початок XIX ст. ознаменувався бурхливим розвитком капіталізму що був прискорений промисловим переворотом. Розвиток капіталістичних відносин супроводжувався занепадом і розкладом дрібного виро
17333. ЕКОНОМІЧНІ ВЧЕННЯ ЗАХІДНОЄВРОПЕЙСЬКИХ СОЦІАЛІСТІВ-УТОПІСТІВ 150 KB
  ЕКОНОМІЧНІ ВЧЕННЯ ЗАХІДНОЄВРОПЕЙСЬКИХ СОЦІАЛІСТІВУТОПІСТІВ Економічна теорія особлива форма переосмислення дійсності з метою її вдосконалення. Вона завжди виходила з того що економічне життя суспільства є базовим щодо інших сторін суспільного буття і виз...
17334. ВИНИКНЕННЯ АЛЬТЕРНАТИВНОЇ ШКОЛИ ПОЛІТИЧНОЇ ЕКОНОМІЇ. НІМЕЦЬКА НАЦІОНАЛЬНА ПОЛІТЕКОНОМІЯ 146 KB
  Виникнення альтернативної школи політичної економії. Німецька національна політекономія У XIX cт. доктрина Адама Сміта користувалася загальним визнанням залишаючи далеко позаду інші економічні теорії. Хоча послідовники класичної школи пропонували власні кор
17335. МАРЖИНАЛІЗМ. СТАНОВЛЕННЯ НЕОКЛАСИЧНОЇ ТРАДИЦІЇ В ЕКОНОМІЧНІЙ ТЕОРІЇ 181.5 KB
  МАРЖИНАЛІЗМ. СТАНОВЛЕННЯ НЕОКЛАСИЧНОЇ ТРАДИЦІЇ В ЕКОНОМІЧНІЙ ТЕОРІЇ В останній третині ХІХ ст. в економічній теорії виникла нова течія маржиналізм яка згодом стала визначальним напрямом розвитку політичної економії. Обєктивна зумовленість її появи поляга
17336. ЕКОНОМІЧНА ДУМКА В РОСІЇ 174 KB
  ЕКОНОМІЧНА ДУМКА В РОСІЇ На стані російської суспільної у тім числі економічної думки ХІХ ст. позначились особливості історичного розвитку країни. Якщо на Заході економічна думка вирішувала проблеми капіталізму як реально існуючого способу виробництва то прогре...