Написать функцию, которая рекурсивно вычисляет сумму чисел в заданном диапазоне
Вводится число и символ (в main), функция выводит линию из символов.
Написать программу, которая запрашивает у пользователя целое число, на экран выводит сколько цифр в числе, их сумму и вывод цифр наоборот (пример: 4356 – 4 цифры, сумма: 4+3+5+6=18, вывод наоборот: 6534) Разработать рекурсивную функцию, которая решает эту задачу!
Линейный поиск.
В данном уроке пойдет речь об алгоритмах поиска и сортировки. Вы, наверняка, уже успели столкнуться с необходимостью упорядочить свой массив или быстро найти в нем какие-то данные. Что ж, сегодня мы попытаемся помочь вам автоматизировать данные процессы.
Для начала, мы рассмотрим наиболее простой из способов поиска данных - линейный поиск.
Данный алгоритм сравнивает каждый элемент массива с ключом, предоставленным для поиска. Наш экспериментальный массив не упорядочен и, может сложиться ситуация, при которой отыскиваемое значение окажется первым в массиве. Но, в общем и целом, программа, реализующая линейный поиск, сравнит с ключом поиска половину элементов массива.
#include <iostream> using namespace std;
int LinearSearch (int array[], int size, int key){ for(int i=0;i<size;i++) if(array[i] == key) return i; return -1; } void main() { const int arraySize=100; int a[arraySize], searchKey, element; for(int x=0;x<arraySize;x++) a[x]=2*x;
//Следующая строка выводит на экран сообщение //Введите ключ поиска: cout<<"Please, enter the key: "; cin>>searchKey; element=LinearSearch(a, arraySize, searchKey);
if(element!=-1) //Следующая строка выводит на экран сообщение //Найдено значение в элементе cout<<"\nThe key was found in element "<<element<<'\n'; //Следующая строка выводит на экран сообщение //Значение не найдено else cout<<"\nValue not found "; } |
Заметим, что алгоритм линейного поиска отлично работает только для небольших или неупорядоченных массивов и является абсолютно надежным.
Линейный поиск в массивах
Программисту часто приходится работать с большими объемами данных, сохраняемых в массивах. Нередко требуется определить, содержит ли массив значение, совпадающее с некоторым ключевым значением. Процесс нахождения в массиве конкретного элемента называется поиском. В этом разделе мы обсудим простой линейный поиск.
Линейный поиск
При линейном поиске каждый элемент массива сравнивается с ключом поиска. Поскольку массив не предполагается упорядоченным каким-либо определенным образом, вероятность встретить искомое значение в первом элементе такая же, как в последнем. В среднем, следовательно, программа должна будет сравнить ключ поиска с половиной элементов массива. Чтобы определить, что значение в массиве отсутствует, программе потребуется сравнить ключ поиска со всеми элементами массива.
Линейный метод поиска хорошо работает с небольшими или несортированными массивами (т. е. не упорядоченными каким-либо определенным образом). Однако для больших массивов линейный поиск неэффективен. Если массив сортирован (например, в восходящем порядке), вы можете воспользоваться высокоскоростной методикой двоичного поиска (en.wikipedia.org/wiki/Binary_search).
Линейный поиск, как правило, является первым алгоритмом поиска, с которым знакомиться программист, что вызвано его чрезвычайно простой реализацией.
Слово «линейный» содержит в себе основную идею метода. На некоторой последовательности поочередно просматриваются элементы, каждый из которых сравнивается с искомым, если они тождественны, то поиск заканчивается. В лучшем случае предстоит произвести всего одно сравнение, а в худшем n, где n — количество элементов в списке.
Ниже, на примере фигур, наглядно демонстрируется работа алгоритма линейного поиска. В качестве искомого элемента (в данном случае это квадрат) задается фигура, и она поочередно сравнивается со всеми имеющимися фигурами до тех пор, пока не будет найдена тождественная ей фигура или окажется, что среди множества элементов таковой нет
Алгоритм линейного поиска не часто используется на практике, поскольку принцип работы «в лоб» делает скорость решения им задачи очень низкой. Линейный поиск сравнивает каждый элемент массива с ключом поиска. Поскольку массив не упорядочен, вполне вероятно, что отыскиваемое значение окажется первым элементом массива. Но, в среднем, программа должна сравнить с ключом поиска половину элементов массива.
#include <iostream>
#include <time.h>
using namespace std;
int LinearSearch(int [], int, int);
void main()
{
srand (time(0));
setlocale (LC_CTYPE, "russian");
const int arraySize = 10;
int a[arraySize], searchKey;
for( int x = 0; x < arraySize; x++)
{
a[x] = rand()%10;
cout << a[x] << " ";
}
cout << "\nВведите ключ поиска: ";
cin >> searchKey;
if (LinearSearch(a, arraySize, searchKey) != -1)
cout << "\nНайдено значение в элементе " << LinearSearch(a, arraySize, searchKey) << '\n';
else cout << "\nЗначение не найдено\n";
}
int LinearSearch (int array[], int size, int key)
{
for (int i = 0; i < size; i++)
{
if(array[i] == key)
return i;
}
return -1;
}
В return стоит -1 потому что -1 не является индексом ни одного элемента массива, если будет другое число, то элемент с таким индексом находится не будет.
Линейный поиск в массивах, или как его ещё называют, поиск в ЛОБ эффективен в массивах, с небольшим количеством элементов, причём элементы в таких массивах никак не отсортированы и не упорядочены. Алгоритм линейного поиска в массивах последовательно проверяет все элементы массива и сравнивает их с ключевым значением. Таким образом, в среднем необходимо проверить половину значений в массиве, чтобы найти искомое значение. Чтобы убедиться, в отсутствии искомого значения необходимо проверить все элементы массива.