Задачи для самостоятельного решения. 1.2.2.1. в последовательности из n целых чисел найти самую длинную строго возрастающую цепочку, т.е
1.2.2.1. в последовательности из n целых чисел найти самую длинную строго возрастающую цепочку, т.е. такую цепочку элементов, что Ai < Ai+1 < Ai+2 и т.д. Напечатать длину этой цепочки. В первой строке задаётся количество чисел в последовательности, а во второй - сами числа.
Исходные данные:
1 5 1 2 3
Результат:
1.2.2.2. в последовательности из n целых чисел найти самую длинную пилу, т.е. такую цепочку элементов, что Ai < Ai+1 > Ai+2 и т.д. или Ai > Ai+1 < Ai+2… В первой строке задаётся количество чисел в последовательности, а во второй - сами числа.
Исходные данные:
1 5 1 2 3
Результат:
1.2.2.3. для заданного числа n найти ближайшее сверху число Фибоначчи (большее или равное)
Исходные данные:
Результат:
1.2.2.4. для заданного числа n найти ближайшее снизу число Фибоначчи (меньшее или равное)
Исходные данные:
Результат:
1.2.2.5. в последовательности из n целых чисел найти пару с самым большим произведением и напечатать его. В первой строке задаётся количество чисел в последовательности, а во второй - сами числа.
Исходные данные:
1 5 1 2 -3
Результат:
1.2.2.6. в последовательности из n целых чисел найти пару с самым большим произведением, которое делится на 21, и напечатать его. В первой строке задаётся количество чисел в последовательности, а во второй - сами числа.
Исходные данные:
1 5 14 2 3
Результат:
1.2.2.7. в последовательности из n целых чисел найти пару с самым большим (маленьким) произведением, но их номера в последовательности должны отличаться не менее, чем на 5. и напечатать его. В первой строке задаётся количество чисел в последовательности, а во второй - сами числа.
Исходные данные:
2 5 1 2 3 7 3 1 2
Результат:
1.2.2.8. в последовательности из n целых чисел найти пару с самым большим (маленьким) чётным произведением, но их номера в последовательности должны отличаться не менее, чем на 5, и напечатать это произведение. В первой строке задаётся количество чисел в последовательности, а во второй - сами числа.
1.2.2.9. Представить данное число n в виде суммы нескольких разных чисел Фибоначчи и напечатать их в порядке убывания (возрастания).
Исходные данные:
Результат:
13 5 1
1.2.2.10. В последовательности из n целых чисел найти наибольший перепад – наибольшую разность элементов в цепочке возрастающих или убывающих элементов. В первой строке задаётся количество чисел в последовательности, а во второй - сами числа.
Исходные данные:
2 5 1 2 3 7 3 2 2
Результат:
1.2.2.11. Требуется найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц. В единственной строке записана последовательность нулей и единиц (без пробелов). Суммарное количество цифр не превышает 1000.
Вывести искомую длину цепочки нулей.
Исходные данные:
Результат:
Продвинутые задачки.
1.2.3.1. Обобщение ряда Фибоначчи. Дана бесконечная в обе стороны последовательность вещественных чисел, которая строится по правилу ai=ai-1+ ai-2. Заданы значения двух произвольных членов этой последовательности ai и aj. Написать программу, которая по заданному числу n вычисляет элемент an. В первой строке задаются номер i и значение ai, во второй номер j и значение aj, в третьей – номер n.
Исходные данные:
Результат:
1.2.3.2. В последовательности цифр a1, a2,...ai,... каждый член, начиная с четвертого, равен последней цифре суммы трех предыдущих. Написать программу, которая по заданным значениям a1, a2, a3 вычисляет an, где n<=1000000000.
Исходные данные:
Результат:
1.2.3.3. Общее количество цифр. Для заданного натурального числа n вычислить и напечатать общее количество цифр во всех числах от 1 до n.
Исходные данные:
Результат:
1.2.3.4. Количество цифр. Для заданного натурального числа n вычислить и напечатать количество каждой цифры во всех числах от 1 до n: количество ноликов, единичек и т.д. до девяти.
Исходные данные:
Результат:
1 10 2 2 2 2 2 2 1 1
1.2.3.5. Минимальная вместимость автобуса. На автобусном маршруте имеется n остановок. На каждой остановке из автобуса сначала выходят ai человек, потом входят bi человек. Изначально автобус пустой. Определить и напечатать минимальную возможную вместимость автобуса.
Исходные данные:
Результат:
Тема 1.3. Массивы
Цель.
Изучение алгоритмов обработки большого количества данных, хранящихся одновременно в оперативной памяти.
Основные понятия.
Массив – упорядоченное множество однотипных элементов, занимающих смежные участки оперативной памяти. Они используются в тех случаях, когда элементы последовательности должны обрабатываться не в том порядке, в котором поступают в программу, или каждый элемент должен обрабатываться (просматриваться) несколько раз. Имя массива ассоциируется с адресом начала массива (первого элемента). Этот адрес является постоянным. Основная операция над массивами – операция доступа к элементу []. Можно использовать значение элемента и можно его изменять. Используя адреса можно обращаться к элементам массива с помощью операции * и операции адресной арифметики.
Ввод и вывод массивов осуществляется поэлементно (для символьных строк – см. ниже).
Ключевые слова.
Массив, индекс, элемент, счётчик, адрес, указатель, NULL, случайное число.
ПРИМЕР 1.
Дан массив целых чисел из N элементов. Для заданных номеров k1 и k2 (1 <= k1 <= k2 <= N) переставить элементы массива от k1-го до k2-го в обратном порядке.
Алгоритм.
В цикле запустим два счётчика навстречу друг другу и соответствующие элементы будем менять местами.
Решение.
// C++
# include <iostream>
# include <cstdlib>
using namespace std;
const int N = 10000;
int main () // основная часть программы – главная функция
{
setlocale (LC_ALL, "RUS");
cout << "Переворот части массива." << endl;
cout << "Введите количество, а в следующей строке числа." << endl;
int a [N], n;
cin >> n;
for ( int i=0; i < n; i++ )
cin >> a [i];
cout << "С какой позицию по какую: ";
int k1, k2;
cin >> k1 >> k2;
k1--, k2--;
for ( int i=k1, j=k2; i < j; i++, j-- )
swap (a [i], a [j]);
for ( int i=0; i < n; i++ )
cout << a [i] << " ";
cout << endl;
system ("PAUSE");
return 0;
}
// C#
using System;
class Program
{
static void Main (string [] args)
{
Console.WriteLine ("Переворот части массива.");
Console.WriteLine ("Введите количество, а в следующей строке числа.");
int n = int.Parse (Console.ReadLine ());
int [] a = new int [n];
string ss = Console.ReadLine (); // все числа в одной строке
string [] s = ss.Split (' '); //| через один пробел
for ( int i=0; i < n; i++ )
a [i] = int.Parse (s [i]);
Console.WriteLine ("С какой позицию по какую: ");
int k1 = int.Parse (Console.ReadLine ());
int k2 = int.Parse (Console.ReadLine ());
k1--, k2--;
for ( int i=k1, j=k2; i < j; i++, j-- )
{
int temp = a [i];
a [i] = a [j];
a [j] = temp;
}
for ( int i=0; i < n; i++ ) // печатаем числа в одну строку
Console.Write (a [i] + " ");
Console.ReadKey ();
}
}
ПРИМЕР 2.
Заполнить массив случайными целыми числами в диапазоне от 0 до 999 и распечатать его.
Решение.
// C++
# include <iostream>
# include <cstdlib>
using namespace std;
const int N = 1000;
int main ()
{
setlocale (LC_ALL, "RUS");
cout << "Заполнение массива случайными числами." << endl;
cout << "Введите количество элементов." << endl;
int * a, n;
cin >> n;
a = new int [n];
srand (time (0));
for ( int i=0; i < n; i++ )
a [i] = rand () % N;
for ( int i=0; i < n; i++ )
cout << a [i] << " ";
cout << endl;
system ("PAUSE");
return 0;
}
// C#
using System;
class Program
{
static void Main (string [] args)
{
Console.WriteLine ("Заполнение массива случайными числами.");
Console.WriteLine ("Введите количество элементов.");
int n = int.Parse (Console.ReadLine ());
int [] a = new int [n];
// заполнение случайными числами
Random rnd = new Random(DateTime.Now.Millisecond);
//создание генератора случайных чисел и инициализация текущим временем
for ( int i=0; i < a.GetLength (0); i++ )
a [i] = rnd.Next ();
// GetLength(i) возращает длину массива по i-му измерению
for ( int i=0; i < n; i++ ) // печатаем числа в одну строку
Console.Write (a [i] + " ");
Console.ReadKey ();
}
}