Составьте алгоритм упорядочения значений трех переменных по возрастанию, т. е. при любых исходных значениях A, B, C отсортируйте их так, чтобы стало: A <= B <= C. Проверьте алгоритм трассировкой при разных вариантах значений исходных данных.
алг Задача-9 вещ A, B, C, X нач ввод A, B, C если A>В то если B>С X:=A A:=C C:=X иначе если C<А то X:=A A:=B B:=C C:=X иначе X:=B B:=A A:=X кв кв иначе если C<А то X:=B B:=A A:=C C:=X иначе если C<В то X:=B B:=C C:=X кв кв кв вывод A, B, C кон
Трассировка при разных вариантах значений исходных данных:
2 to 3 comparisons, 0 to ~1.7 swaps
Old question, new answer… The following algorithm sorts x, y and z with 2 to 3 comparisons depending on their values and 0 to ~1.7 swap operations.
void sort3(K& x, K& y, K& z)
{
if (y < x) {
if (z < x) {
if (z < y) {
swap(x, z);
} else {
K tmp = std::move(x);
x = std::move(y);
y = std::move(z);
z = std::move(tmp);
}
} else {
swap(x, y);
}
} else {
if (z < y) {
if (z < x) {
K tmp = std::move(z);
z = std::move(y);
y = std::move(x);
x = std::move(tmp);
} else {
swap(y, z);
}
}
}
}
So, how does it work? It’s basiccaly an unrolled insertion sort: if the values are already sorted (it takes 2 comparisons to check that) then the algorithm does not swap anything. Otherwise, it performs 1 or 2 swap operations. However, when 2 swap operations are required, the algorithm « rotates » the values instead so that 4 moves are performed instead of 6 (a swap operation should cost 3 moves, unless optimized).
There are only 6 possible permutations of 3 values. This algorithm does the comparisons needed to know which permutation we’re treating. Then it does the swapping and leaves. Therefore, the algorithm has 6 possible paths (including the one where it does nothing because the array is already sorted). While it’s still human-readable, an equivalently optimal algorithm to sort 4 values would have 24 different paths and would be much harder to read (for n values, there are n! possible permutations).
Since we’re already in 2015 and you seemed to be using C++, I took the liberty use std::move so to make sure that the swap-rotate thingy would be efficient enough and would work even for moveable but non-copyable types.
Перейти к контенту
§ 12 Алгоритмы с ветвящейся структурой ГДЗ по Информатике 9 класс. Семакин
9. Составьте алгоритм упорядочения значений трех переменных по возрастанию, т. е. при любых исходных значениях А, B, С отсортируйте их так, чтобы стало: А ≤ В ≤ С. Проверьте алгоритм трассировкой при разных вариантах значений исходных данных.
Ответ
Алг СОРТИРОВКА-3 Program SORT_3;
вещ А, В, С, X var A,B,C,X: real;
нач begin
ввод А, В, С readln (А, В, С);
если А > В if A > В
то then begin
X := А; X := А;
А := В; А := В;
В := X В := X
kb end;
если В > С if В > С
то then begin
X := В; X := В;
В := С; В := С;
С := X С := X
kb end;
если А > В if A > В
то then begin
X := А; X := А;
А := В; А := В;
В := X В := X
kb end;
вывод А,В,С write(А,В,С)
кон end.
procedure swap(var a, b: real);
var t: real;
begin
t := a;
a := b;
b := t;
end;
var a, b, c: real;
begin
readln(a, b, c);
if (a > b) then swap(a, b);
if (b > c) then swap(b, c);
if (a > b) then swap(a, b);
writeln(a, ‘ ‘, b, ‘ ‘, c);
end.
===========================
Без процедур:
var a, b, c, t: integer;
begin
readln(a, b, c);
if (a > b) then
begin
t := a;
a := b;
b := t;
end;
if (b > c) then
begin
t := b;
b := c;
c := t;
end;
if (a > b) then
begin
t := a;
a := b;
b := t;
end;
writeln(a, ‘ ‘, b, ‘ ‘, c);
end.
Помогите создать алгоритм на языке Паскаль
.
Профи
(798),
закрыт
10 лет назад
составьте алгоритм упорядочения значений трех переменных по возрастанию, т. е. при любых исходных значениях А, В, С отсортируйте их так, чтобы стало; А
Jurii
Высший разум
(175100)
10 лет назад
По возрастанию не всегда возможно!
К примеру набор чисел 5 5 8 ни как не отсортировать по возрастанию.
Но по «неубванию» они отсортированы.
Алгоритм таков:
1) Ввести значения A, B, C
2) Если A > B Тогда Поменять значения A и B
3) Если A > B Тогда Поменять значения B и C
4) Если A > B Тогда Поменять значения A и B
Всё!
Значения A, B и C отсортированы в порядке неубывания!
