Задача 90. В заданном массиве подсчитать количество чисел между первым вхождением максимального и последним вхождением минимального элемента массива

 

// Программа отлажена в Visual Studio 2005

#include "stdafx.h"

#include<conio.h>

#include<iostream>

using namespace std;

 

int count (float a[], int n);

int main()

{

int k;

float a[]={10,3,18,3,19,6,25,7,25,4,5,4,11};

// float a[]={3,3,3,3,3,3,3,3,3};

int n=sizeof(a)/sizeof(float);

 

k=count (a, n);

 

cout<<"Всего чисел между max и min => "<<k;

getch(); return 0;

}

 

// функция обработки массива

int count (float a[], int n)

{ int i, nmin=0, nmax=0, tmp;

float min=a[0], max=a[0];

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

if(a[i] > max)

{ max=a[i]; nmax=i;} // первый максимум

cout<<max<<' '<<nmax<<'\n';

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

if(a[i] <= min)

{ min=a[i]; nmin=i; } // последний минимум

cout<<min<<' '<<nmin<<'\n';

if(nmax > nmin)

{ tmp=nmax; nmax=nmin; nmin=tmp;}

 

tmp=0;

for(i=nmax+1; i < nmin; i++)

tmp++;

return tmp;

}

 

 

Задача 91. Ввести массив из произвольного количества чисел (но не более заданного числа). Отсортировать его методом «пузырька» по неубыванию, выводя на экран все промежуточные и окончательный вари­анты.

 

Поясним суть упорядочения элементов массива указанным методом, реализованным ниже в функции bubble(). Во внешнем цикле (индекс i) фиксируется начальный элемент массива (x[i]); затем во внутреннем цикле (индекс k) выбранный элемент последовательно сравниваеся со всеми остальными элементами массива и переставляется местами с теми из них, которые меньше начального элемента. Таком образом, за один оборот внешнего цикла минимальный элемент массива оказывается на первом месте и в дальнейших рассмотрениях не участвует. Теперь во внешнем цикле за начальный выбирается второй элемент массива и описанная выше процедура повторяется для оставшейся части массива: на втором месте оказывается минимальный элемент из оставшихся. Так продолжается вплоть до предпоследнего элемента массива, пока весь массив не станет упорядоченным. орой икле за отрениях не участвует. альный элемент массива оказывается на пером мента в маас

 

// Программа отлажена в Visual Studio 2008

#include "stdafx.h"

#include <iostream>

#include <conio.h>

using namespace std;

 

const int n=1000;

// Функция сортировка массива по неубыванию методом пузырька

void bubble(float x[], int m)

{

int i, k, r; float p;

for(i=0; i < m-1; i++)

{

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

{

if(x[i]>x[k])

{

p=x[i];

x[i]=x[k];

x[k]=p;

}

}

for(r=0; r < m; r++)

cout<<" "<<x[r];

cout<<"\n";

}

}

 

int main()

{

int m=0,i,k; float a[n];

do

{

cout<<"Введите длину массива (не более 1000): "; cin>>m;

}

while (m>1000);

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

{

cout<<"Введите a["<<i+1<<"] = "; cin>>a[i];

}

//****************//

bubble(a, m);

//****************//

cout<<"\n"<<"Массив отсортирован: ";

for(k=0; k<m; k++) cout<<"\n"<<"a["<<k+1<<"] = "<<a[k];

getch(); return 0;

}

 

Задача 92. Вводится упорядоченный по неубыванию массив из M чисел. Используется метод бинарного поиска ключевого элемента.

 

Поясним суть бинарного (двоичного) поиска, который реализует функция bpoisk(). Функция bpoisk() работает с массивом, элементы которого отсортированы по возрастанию. Определяется индекс “срединного ” элемента mid и его значение x[mid] сравнивается с ключом поиска Q. В случае несовпадения сравниваемых элементов отбрасывается та часть рассматриваемого массива, в которой искомого элемента заведомо быть не может (берется во внимание упорядоченность массива). Теперь к оставшейся части массива снова применяется только что описанная процедура. Так продолжается, пока не будет обнаружен искомый элемент массива, либо выяснится, что такого элемента в масweо быть не может ()овина маив обороте внешнего сиве нет, когда весь массив исчерпается.

 

#include <iostream.h>

#include <conio.h>

//Функция бинарного поиска

int bpoisk(int x[], int n, int Q)

{

int low=0, mid, high=n-1;

while (low<=high)

{

mid=(low+high)/2;

if (Q==x[mid])

return mid;

Else

if (x[mid]<Q)

low=mid+1;

Else

high=mid-1;

}

return -1;

}

// Главная

const int m=10;

int main()

{

int Q, t, i; int a[m];

cout<<"Введите массив:"<<”\n”;

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

{

cout<<"Введите a["<<i+1<<"] = "; cin>>a[i];

}

cout<<"Введите искомое число: ";

cin>>Q;

//**********************

t=bpoisk(a, m, Q);

//**********************

if (t>=0)

cout<<Q<<" на "<<t+1<<"-ом месте.";

Else

cout<<Q<<" не найден.";

getch(); return 0;

}

 

 

Задача 93. Ввести неупорядоченный массив из M чисел. Отсортировать его методом последовательного сравнения смежных пар, а затем использовать метод бинарного поиска ключевого элемента.

 

Дадим некоторые предварительные пояснения. Во внутреннем цикле (for(int i=0;…)) функции sort_sp() последовательно сравниваются все пары соседних элементов и меняются местами, если они не упорядочены по возрастанию. За один оборот внешнего цикла (do – while)максимальный элемент из рассматриваемого множества чисел окажется на последнем, (n-1)–м месте и в дальнейших сравнениях он не участвует: при каждом обороте внешнего цикла количество сравниваемых во внутреннем цикле элементов уменьшается на единицу (n--;). Так происходит, пока во внешнем цикле не исчерпается весь массив (n=0). Однако возможно “ досрочное ” завершение сортировки, если на некотором шаге во внутреннем цикле не было ни одной перестановки элементов. Об этом сигнализирует состояние флага flag.

 

// Программа отлажена в Visual Studio 2008

#include "stdafx.h"

#include <iostream>

#include <conio.h>

using namespace std;

 

// функция сортировки сравнением смежных пар

void sort_sp(int x[], int n)

{ int flag;

do

{ n--; flag=0; // флаг, возможно, досрочного завершения

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

if(x[i]>x[i+1])

{ int r=x[i];

x[i]=x[i+1];

x[i+1]=r;

flag=1;

}

}

while(n!= 0 && flag);

return;

}

// Функция бинарного поиска.

int bpoisk(int x[], int n, int Q)

{

int low=0, mid, high=n-1;

while(low<=high)

{

mid=(low+high)/2; //Середина массива

 

if(Q==x[mid])

return mid;

else

if(x[mid]<Q)

low=mid+1;

else

high=mid-1;

}

return -1;

}

 

// Главная

const int m=10;

int main()

{

int Q, t, i; int a[m];

setlocale(NULL, ".1251");

cout<<"Введи первичный массив(10 чисел)\n ";

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

cin>>a[i];

cout<<"Введи искомое число: ";

cin>>Q;

//**************************

sort_sp (a, m);

//**************************

cout<<"Отсортированный массив: "<<endl;

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

cout<<" "<<a[i];

cout<<"\n";

//**************************

t=bpoisk(a, m, Q);

//**************************

if(t>=0)

cout<<Q<<" на "<<t+1<<"-ом месте.";

else

cout<<Q<<" не найден.";

getch(); return 0;

}

 

Задача 94. Программа, используя функцию razn(), подсчитывает количество различных чисел в массиве.

 

// Программа отлажена в Visual Studio 2008

#include "stdafx.h"

#include<stdio.h>

#include<conio.h>

// функция подсчитывает количество различных

// чисел в массиве

int razn(int x[], int m)

{

int i,j,k=1;

for(i=0; i<m-1; i++)

{

for(j=i+1;j<m;j++)

if(x[i]==x[j])

break;

if(j==m)

k++;

}

return k;

}

 

int main()

{

int a[]={0,9,5,7,5,7,9,0};

int n=sizeof(a)/sizeof(int);

printf("В массиве %d различных чисел\n",razn(a,n));

getch(); return 0;

}

 

 

Задача 95. Программа выводит на экран те элементы массива, которые встречаются в нём только по одному разу.

 

// Программа отлажена в Visual Studio 2008

#include <iostream>

#include <conio.h>

using namespace std;

 

const int m = 10;

int main()

{

int a[m]={3,7,6,1,5,7,6,9,5,7},i,k;

cout<<"Встречаются в массиве один раз:"<<endl;

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

{

k=0;

while(k<m)

{

if(a[k]==a[i] && i!=k)

break;

k++;

}

if(k==m) //цикл не завершился досрочно?

cout<<"a["<<i<<"]="<<a[i]<<endl;

}

getch(); return 0;

}