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[].


 

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

82973. ДЕЗИНФЕКЦИЯ. СВЕДЕНИЯ ПО ВЕТЕРИНАРНОЙ САНИТАРИИ И ДЕЗИНФЕКЦИИ 52.66 KB
  Дезинфекция слагается из двух последовательно осуществляемых приемов: механической очистки и собственно дезинфекции.Удалением загрязнений создают условия для последующего свободного доступа химических средств в случае проведения дезинфекции к оставшимся на поверхностях микроорганизмам...
82974. Опухолевая прогрессия. Метастазирование, кахексия, рецидирование опухолей 47 KB
  Злокачественные опухоли зачастую становятся причинами смерти людей. Согласно цитологической и гистологической структуре опухолевых клеток и тканей выделяют доброкачественные и злокачественные опухоли. Доброкачественные опухоли. Такие опухоли растут медленно и как правило не метастазируют.
82975. Антропогенные факторы загрязнения гидросферы 45.11 KB
  Существование всего живого на земле и человека в частности основано на использовании воды. Установлено что более 400 видов веществ могут вызвать загрязнение воды. Постоянно загрязняются и подземные воды при просачивании промышленных и хозяйственно-бытовых стоков из хранилищ накопителей отстойников...
82976. Узагальнення та систематизація знань по темі «Поняття» 136 KB
  Систематизувати знання про поняття вдосконалювати вміння розв’язувати логічні задачі класифікувати та порівнювати предмети. Сьогодні ми закріпимо і узагальнимо наші знання з теми Поняття. Побудова Асоціативного куща спираючись на знання дітей по темі Поняття.
82977. Виготовлення геометричних фігур при допомозі аплікації. Порівняння фігур за кольором, розміром, формою 1.67 MB
  Мета: вчити виготовляти геометричні фігури з паперу за допомогою аплікаціїпорівнювати фігури за кольором формою розміром; розвивати розумові здібності мовлення творчі здібності учнів; виховувати любов до своєї родини; допомогти дитині зрозуміти які цінності є духовним фундаментом повноцінної...
82978. Творимо казковий світ «Кольорочас». We create the world of wonder «Colourtime» 623.5 KB
  Мета: географія ознайомити учнів з етапами формування української нації;сформувати в учнів поняття про національний склад населення та пояснити причини його строкатості; назвати етнографічні групи українців та національні меншини; обґрунтувати географію розміщення історико географічних етнографічних...
82979. Казки народів світу, Ш. Перро «Кіт у чоботях» 1.58 MB
  Мета: Продовжити знайомство з казками народів світу. Формувати в учнів уміння повно, точно, емоційно робити висновки і висловлювати судження про прочитане та посилатися під час відповіді на текст книжки; активізувати читацьку пам’ять; збагачувати словниковий запас...
82980. Речення. Види речень за метою висловлювання 913 KB
  Мета: Допомогти глибше усвідомити поняття мета висловлювання; з’ясувати які будуть речення за метою висловлювання; формувати вміння визначати види речень за метою висловлювання; будувати речення різних типів; відпрацьовувати навички грамотного письма; розвивати навички зв’язного мовлення...
82981. Людина серед людей. Норми поведінки. Вихованість 126 KB
  Освітній продукт: колективно створений ілюстрований довідник Людина серед людей. Людина серед людей. В усі часи ще з самого початку виникнення на Землі Людини вона почала замислюватися над своїм призначенням в житті над своїм значенням для інших людей і всього світу.