М
Молодежь
К
Компьютеры-и-электроника
Д
Дом-и-сад
С
Стиль-и-уход-за-собой
П
Праздники-и-традиции
Т
Транспорт
П
Путешествия
С
Семейная-жизнь
Ф
Философия-и-религия
Б
Без категории
М
Мир-работы
Х
Хобби-и-рукоделие
И
Искусство-и-развлечения
В
Взаимоотношения
З
Здоровье
К
Кулинария-и-гостеприимство
Ф
Финансы-и-бизнес
П
Питомцы-и-животные
О
Образование
О
Образование-и-коммуникации
anastejsablek
anastejsablek
04.12.2020 08:51 •  Информатика

Напишите программу, которая сортирует массив и находит количество различных чисел в нем. используйте алгоритм быстрой сортировки. пример: массив: 5 3 4 2 1 6 3 2 4 после сортировки: 1 2 2 3 3 4 4 5 6 различных чисел: 5

👇
Ответ:

//PascalABC.NET версия 3.4.2.1991 от 03.03.19

//Если программа не запускается, то обновите версию

const

   handsfree = true;

   nmax = 100;

   random_min = -50;

   random_max = 50;

var

   a: array[1..nmax] of real;

   i, n, count: integer;

procedure QuickSort(first, last: Integer);{ Быстрая сортировка массива A[] , использует массив как глобальную переменную}

var

   i, j: integer;

   x, y: real;

begin

   i := first;

   j := last;

   x := a[(first + last) div 2];

   repeat

       while (A[i] < x) do inc(i);

       while (x < A[j]) do dec(j);

       if (i <= j) then

       begin

           y := A[i]; a[i] := a[j]; a[j] := y;

           inc(i); dec(j);

       end;

   until (i > j);

   if (first < j) then QuickSort(first, j);

   if (i < last) then QuickSort(i, last);

end;

begin

   {ввод массива}

   n := nmax;

   if handsfree then begin

       n := random(nmax - 5) + 5;

       for i := 1 to n do

       begin

           a[i] := random(random_max - random_min) + random_min;

           write(a[i], ' ');

       end

   end

   else begin

       write('n = ');

       readln(n);

       for i := 1 to n do

           readln(a[i]);

   end;

   writeln();

   

   QuickSort(1, n);

   

   {вывод массива}

   writeln('Вывод массива[', n, ']:');

   for i := 1 to n do

       write(a[i], ' ');

   writeln();

   

   {подсчет разных}

   count := 1; {первый элемент точно разный}

   for i := 2 to n do

       if a[i] <> a[i - 1] then

           count := count + 1;

   writeln('Разных элементов = ', count);

end.

4,6(65 оценок)
Открыть все ответы
Ответ:
honeybeyker
honeybeyker
04.12.2020
Алгоритм. Отсортируем массив за O(nlogn). Запустим цикл по всем k, в теле цикла будем искать индексы i <= j, такие, что A[i] + A[j] = -A[k]. Понятно, что этот поиск надо делать за O(n), чтобы общее время работы было квадратичным.

Искать будем с двух указателей. Рассмотрим кусок массива, в котором ищем ответ A[l..r] (первоначально l = 1, r = n). Посмотрим на A[l] + A[r]. Если эта сумма больше, чем нужно, уменьшим на 1 число r, если меньше - увеличим на 1 число l, если равно -A[k] - победа, выводим ответ (l, r, k). Будем повторять это в цикле, пока l не станет больше r.

Если после выполнения цикла по k искомая тройка так и не нашлась, пишем "нет".

Корректность. Пусть в какой-то момент A[l] + A[r] < -A[k]. Тогда, чтобы иметь возможность получить A[i] + A[j] = -A[k], надо сумму увеличить. A[l] оказалось настолько мало, что даже если прибавить к нему самое большое возможное число (а это как раз A[r] - массив-то отсортирован!), то всё равно получается слишком мало. Значит, A[l] в ответе не будет, и можно безбоязненно выкинуть его из рассмотрения. Аналогично будет и в случае, когда A[l] + A[r] > -A[k].
Осталось показать, что если такая тройка индексов существует, то наш алгоритм не выдаст неверный ответ "нет". Но это очевидно: если ответ (I, J, K), то уж при k = K алгоритм что-нибудь да найдёт.

Время работы. Внутренний цикл выдает ответ не более чем за линейное время: всякий раз размер массива уменьшается на 1, всего элементов в массиве n, а на каждом шаге тратится константное время; пусть время выполнения внутреннего цикла T'(n) < an. Тогда все n проходов внешнего цикла затратят время T1(n) <= n T'(n) < an^2.
Сортировку можно сделать за время T2(n) < b nlogn < bn^2
Общее время работы T(n) = T1(n) + T2(n) < an^2 + bn^2 = cn^2
4,7(97 оценок)
Ответ:
cratospo234
cratospo234
04.12.2020

#include <iostream>

#include <vector>

#include <fstream>

#include <algorithm>

using namespace std;

class pacient {

private:

 string lastName_m, mOrFM_m, adress_m, diagnosis_m;

public:

 pacient(string lastName = "", string mOrFM = "", string adress = " ", string diagnosis = " ") {

  lastName_m = lastName;

  mOrFM_m = mOrFM;

  adress_m = adress;

  diagnosis_m = diagnosis;

 }

 string getLastName() {

  return lastName_m;

 }

 string getAll() {

  return lastName_m + ", " + mOrFM_m + ", " + adress_m + ", " + diagnosis_m + ".";

 }

};  

int main() {

fstream out("output.txt");

setlocale(LC_ALL, "Russian");

vector<pacient> arr;

for(int i = 0;;++i) {

 string a[4];

 for(int j = 0; j<4; ++j) {

  switch(j) {

   case 0: cout << "Last name: "; break;

   case 1: cout << "Male or FeMale: "; break;

   case 2: cout << "Adress: "; break;

   case 3: cout << "Diagnosis: "; break;

  }

  getline(cin, a[j]);

 }

 pacient temp(a[0], a[1], a[2], a[3]);

 cout << "Для окончания ввода введите 1: ";

 arr.push_back(temp);

 string temp1;

 getline(cin, temp1);

 if(temp1=="1") {

  break;

 }

}

for(int j = 0; j<1000; ++j) {

for(int i = 0; i<arr.size()-1; ++i) {

 if(arr[i].getLastName()[0]>arr[i+1].getLastName()[0]) {

  swap(arr[i], arr[i+1]);

 }

} }

for(int i = 0; i<arr.size(); ++i) {

 cout << arr[i].getLastName() << endl;

 out << arr[i].getAll();

 out << "\n";

}

out.close();

}


С++ Создайте текстовый файл, содержащий сведения о пациентах глазной клиники: фамилия пациента, пол,
С++ Создайте текстовый файл, содержащий сведения о пациентах глазной клиники: фамилия пациента, пол,
4,4(24 оценок)
Новые ответы от MOGZ: Информатика
logo
Вход Регистрация
Что ты хочешь узнать?
Спроси Mozg
Открыть лучший ответ