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


 

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

73895. Электронная тепловая поляризация 123.69 KB
  Тензоры упругости и податливости Приложенные извне механические напряжения Х упруго и обратимо изменяют форму кристалла – происходит его деформация х. Поскольку xmn и Xmn – тензоры второго ранга в анизотропных кристаллах или текстурах можно ожидать что каждая из девяти компонентов деформаций xkp индуктирована девятью компонентами тензора напряжения...
73896. Виникнення класичної буржуазної політичної економії в Англії. 32.5 KB
  Петті Уільям Петті 1623 1687 основоположник класичної політичної економії в Англії. Петті є неоднозначною. У своїх працях особливо ранніх Петті віддає данину меркантилізму. Отже на відміну від меркантилістів які використовували емпіричний описовий метод Петті заклав основи абстрактного методу в політичній економії.
73897. Зародження і проблеми суперечливого розвитку класичної буржуазії політекономії у Франції. 29.5 KB
  Буагільбер У XVII ст. П’єр де Буагільбер 1646 1714 засновник класичної політичної економії у Франції народився в Руані в дворянській сім'ї здобув гарну освіту займався певний час літературною діяльністю потім юриспруденцією. Особливості економічного розвитку Франції позначилися на формуванні економічних поглядів Буагільбера. 1696 Роздрібна торгівля Франції 1699 Міркування про природу багатства грошей і податків 1707 та інших Буагільбер виступає з гострою критикою меркантилізму.
73898. Виникнення політичної економії в Німеччині. Ф. Ліст, “Стара і нова” історичні школи В. Рошер, К. Кніс, Б. Гільдебранд, Г. Шмолер, В. Зомбард, Брентано 50.5 KB
  Німеччина XIX ст. — це країна, що складалася з політично й економічно відособлених держав, обєднаних у конфедерацію за національною ознакою. їхня економічна відособленість базувалась на феодальних відносинах
73899. Економічна думка Давньої Греції. 34.5 KB
  Проте Ксенофонт як захисник натурального господарства все ж помітив зрослий поділ праці в суспільстві хоча й заперечував об'єктивний недолік який випливав звідси потребу розгортання товарногрошових відносин. Зрівняльний розподіл у філософів та воїнів поєднувався з широким розподілом праці між всіма громадянами. Численні його праці охоплюють найрізноманітніші галузі знання: логіку психологію риторику етику поетику економіку фізику зоологію. Серед визначних його відкриттів у галузі економіки аналіз розвитку форм вартості в...
73900. Начала політичної економії та оподаткування 33 KB
  Давід Рікардо 17721823 рр. Рікардо покладена теорія вартості визначення вартості товару робочим часом. Рікардо і проблему усереднення прибутку та впливу застосованого капіталу на ціноутворення. Рікардо є те що він як і багато його попередників ототожнював робочу силу як товар з його функцією працею.
73901. Економічна думка в Україні в демографічний період 19 століття 45 KB
  Загострення кризи кріпосницької системи зростання селянських заворушень стали поштовхом для розвитку антикріпосницького руху. Значна частина членів товариства яка стояла на ліберальних позиціях заперечувала революційну боротьбу і виступала за еволюційний шлях розвитку. Каразін розробляє проекти господарського розвитку країни в цілому. Каразін прихильник розвитку різних галузей вітчизняної промисловості він закликає дворян організовувати промислові підприємства та сприяє наданню їм фінансової допомоги.
73902. Электроника, конспект лекций. Усилители 8.76 MB
  Загострення кризи кріпосницької системи зростання селянських заворушень стали поштовхом для розвитку антикріпосницького руху. Значна частина членів товариства яка стояла на ліберальних позиціях заперечувала революційну боротьбу і виступала за еволюційний шлях розвитку. Каразін розробляє проекти господарського розвитку країни в цілому. Каразін прихильник розвитку різних галузей вітчизняної промисловості він закликає дворян організовувати промислові підприємства та сприяє наданню їм фінансової допомоги.
73903. Економічне вчення фізіократії. Ф.Кене. А.Р.Ж.Тюрб 49 KB
  Фізіократи — французькі економісти другої половини XVIII ст., представники класичної політичної економії. Поява школи фізіократів зумовлена соціально-економічними умовами тогочасної Франції