отчет 25 (АЯиП отчеты по лабам (кроме 24))
Описание файла
Файл "отчет 25" внутри архива находится в следующих папках: АЯиП отчеты по лабам (кроме 24), Отчеты. Документ из архива "АЯиП отчеты по лабам (кроме 24)", который расположен в категории "". Всё это находится в предмете "информатика" из 2 семестр, которые можно найти в файловом архиве МГТУ им. Н.Э.Баумана. Не смотря на прямую связь этого архива с МГТУ им. Н.Э.Баумана, его также можно найти и в других разделах. Архив можно найти в разделе "лабораторные работы", в предмете "информатика" в общих файлах.
Онлайн просмотр документа "отчет 25"
Текст из документа "отчет 25"
Лабораторная работа 25.
Программирование функций.
Задание: Дан упорядоченный по неубыванию значений элементов массив целых чисел и некоторое целое число b. Написать программу, определяющую место вставки числа b в упорядоченный массив такое, чтобы упорядоченность не нарушилась. Если таких мест несколько – определить ближайшее к началу массива место. Для поиска места воспользоваться алгоритмом дихотомического поиска. Осуществить вставку числа b на его место. При программировании использовать функцию. Вывести на печать исходный и сформированный массив.
Текст программы:
// lab25.cpp : Defines the entry point for the console application.
//Дан упорядоченный по неубыванию значений элементов массив целых
//чисел и некоторое целое число b. Написать программу, определяющую
//место вставки числа b в упорядоченный массив такое, чтобы
//упорядоченность не нарушилась. Если таких мест несколько - определить
//ближайшее к началу массива место. Для поиска места воспользоваться
//алгоритмом дихотомического поиска. Осуществить вставку числа b на
//его место. При программировании использовать функцию. Вывести на
//печать исходный и сформированный массив.
#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <conio.h>
short a[40],n,i=0,b=0,right;
//подпрограмма поиска места и вставки в существующий массив
void vstavka (short &right, short &n)
{
short left;
left=0;
right=n-1;
i=((left+right)/2);
if (b>a[n-1]) i=n-1;
else
if (b<a[0]) i=-1;
else
while (((a[i]>b) || (b>a[i+1])) & (i!=n-1) & (i!=-1))
{
if (b>a[i+1]) left=i;
else right=i;
i=((left+right)/2);
}
right=i+1;
}
//основная программа
int _tmain(int argc, _TCHAR* argv[])
{
//выполняем ввод с одновременной проверкой упорядоченности
printf ("Vvedite razmernost vashego massiva: ");
scanf ("%d",&n);
printf ("\nVvedite massiv razmernosti %d, yporiadochennyi po neybyvaniu:\n",n);
while (i<n)
{
printf ("%d) ",i+1);
scanf (" %d",&a[i]);
if ((i>0) & (a[i]<a[i-1])) //проверка упорядоченности
{
puts ("\nVy vvodite nepravilno, \nmassiv dolzhen bit yporiadochennym po neybyvaniu, \nNACHNITE ZANOVO!\n");
i=-1;
}
i++; //переход обратно в цикл ввода
}
printf ("\nVvedite chislo 'b', kotoroe nado vstavit v massiv: ");
scanf ("%d",&b);
vstavka (right,n);
//Обратным отсчетом сдвигаем элементы, записываем b
for (i=n; i>right;i--)
{
a[i]=a[i-1];
}
a[right]=b;
n++;
puts("\nNovyi massiv:");
for (i=0; i<n; i++)
{
printf ("%d) %d\n",i+1,a[i]);
}
getch();
return 0;
}
Тест:
Схема алгоритма: