(Java) Оператор цикла For. Типовые задачи


Попробуем написать программу для решения следующей задачи:
Найти сумму всех целых чисел от 100 до 500. 

При решении данной задачи возникает трудность в поиске суммы. Если мы будем просто записывать результат сложени в переменную s, например как

s=100+101+102+103+...+500

уйдет очень много времени на саму запись, ведь компьютер не поймет как использовать многоточие в арифметическом выражении и нам прийдется написать все числа от 100 до 500 в эту сумму. Да и ценность такой программы будет ничтожной. Особенно если мы захотим поменять наши числа и взять другой диапазон.

Как же нам поступить?

Если мы обратим внимание на запись выше, то у нас постоянно используется сложение "+".
Можно попробовать добавлять числа к переменной s постепенно. Например, используя такую запись
s=s+i;
что мы здесь сделали:
1) справа мы поставили вычисление выражения s+i, то есть мы берем значение переменной s, которое у нас сейчас в памяти и добавляем к нему значение переменной i
2) слева мы поставили имя переменной s, то есть весь результат вычисления справа будут сохраняться в эту переменную, таким образом мы изменем значение переменной s. 

Где же взять числа из нашего диапазона?

Числа от 100 до 500, которые относятся к нашему диапазону должны поочереди попадать в перемнную i. А это можно сделать с использованием известного нам цикла for
Например, таким образом
s=0;          //в начале необходимо обнулить переменную s, чтобы на первом шаге число 100 добавлялось к нулю, а не к тому что в памяти!
for ( i = 100; i<=500; i++)  //заголовок цикла, в котором переменная i меняет свое значение от 100 до 500 с шагом 1
    s = s + i;   //тело цикла, в котором мы постепенно к переменной s добавляем значение изменяющейся переменной i 
                 // и результат сохраняем обратно в переменной s
Данное решение очень похоже на вычисление суммы по действиям
 s = 0 + 100 = 100
 s = 100 + 101 = 201
 s = 201 + 102  = 303
и т.д.

Максимальное число среди заданных чисел

При изучении условного оператора мы затрагивали тему поиска максимального числа из нескольких введенных чисел. В задаче "Максимум из четырех чисел" мы использовали следующий алгоритм:
1. присвойте значение переменной M первой из четырех переменных;
2. если значение второй переменной больше, чем значение, находящееся в переменной M, то замените значение переменной на значение второй переменной;
3. если значение третьей переменной больше, чем значение, находящееся в переменной M, то замените значение переменной M на значение третьей переменной;
4. если значение четвертой переменной больше, чем значение, находящееся в переменной M, то замените значение переменной на значение четвертой переменной.

Видно, что каждое  число (обозначим его за X) мы сравнивали с переменной M, следующим образом:
 
псевдокод
ввод Х
если (M < X), то
  M = X

Главное в этом коде определить, какое начальное значение будет у переменной M.
Обычно, при решении задачи на поиск максимума или минимума, начальное значение переменной M присваивают равной первому числу.
Таким образом, вышеуказанный код необходимо выполнить на 1 раз меньше, чем количество чисел (т.к. первое число необходимо ввести и сохранить в качестве начального значения переменной M).
Если у нас количество чисел задается с клавиатуры (например, в переменную n), то мы можем организовать цикл (от 2 до n), используя для хранения числа одну и ту же переменную.

Попробуйте написать программу самостоятельно.

Максимальное не среди всех

Если нам необходимо найти максимальное (минимальное) не среди всех вводимых чисел, а только среди чисел, удовлетворяющих определенному условию, то необходимо учитывать тот факт, что первое число, которое мы берем за начальное значение максимума (минимума) не всегда будет удовлетворять нашим требованиям.

Например, если мы ищем максимальное отрицательное число, то имея набор данных: \(\{5, -2, 4, 2, -1, -3\}\) мы получим в начальном значении максимума число 5, а оно положительное и больше любого отрицательного. И, следовательно, условие X > M всегда будет ложно.

Следовательно, в алгоритм из предыдущей задачи недостаточно добавить одну лишь проверку на отрицательное число, необходимо еще учитывать тот факт, что первое число может не удовлетворять требуемому условию (в данном случае быть отрицательным).

Исправить это можно с помощью добавления внутри цикла следующего условия:
 
псевдокод
если X - отрицательное, то
  если M >= 0 или M < X, то
    M = X

В указанном коде условие M >= 0 позволяет выполнить действие M = Х даже в том случае, если первоначально в переменную попало значение, которое заведомо больше остальных (в рассмотренном нами примере - значение равное 5).

Еще заметим, что если диапазон изменения чисел известен, то в качестве начального значения максимума (минимума) можно брать минимальное (максимальное) число из указанного диапазона.

Задача

Дано N чисел. Найти второй по величине максимальный элемент последовательности.

Данная задача допускает два толкования.
Например, если нам дан набор чисел: \(10\ 15\ 20\ 35\ 14\ 35\ 10\), то каким должен быть ответ?
Под "вторым по величине максимальным элементом" или просто "вторым максимумом", можно понимать:
1) значение, которое стояло бы на предпоследнем месте, если бы мы все значения расставили (отсортировали) по неубыванию (каждый следующий больше или равен предыдущему). Тогда для рассмотренного набора чисел ответом будет значение 35;
2) значение элемента, больше которого только максимальный. Тогда ответ - 20.
Если в наборе чисел только один максимальный элемент (все остальные меньше), то оба толкования совпадают, и ответ будет одинаковый для обоих случаев, иначе - ответ будет разный.

Рассмотрим первый случай (алгоритм будем записывать на псевдокоде).
Для нахождения ответа будем использовать две переменные:
1) максимум1 - максимальное значение (первый максимум);
2) максимум2 - второй максимум (наш ответ).

Если диапазон изменения значений известен, то в качестве начальных значений принимаем число, которое заведомо меньше нижней границы диапазона (например, при диапазоне от -1000 до 1000 - берем число -1001)
Если диапазон значений неизвестен, то можно первые два вводимых числа записать в начальные значения переменных максимум1 и максимум2, а затем сравнить эти две переменных.
ввод N //количество чисел
ввод a, б
максимум1 = а
максимум2 = б
если б > а, то
    максимум1 = б
    максимум2 = а

Далее рассматриваем все остальные элементы (первые 2 уже просмотрели, значит начинать будем с 3го)
нц для i от 3 до n
    ввод а
    если а > максимум1 //встретилось значение большее максимума1
      то 
        максимум2 = максимум1 //бывший первый максимум станет вторым
        максимум1 = а  //первым максимумом станет новый элемент
      иначе
        //очередной элемент не больше максимум1
        //его необходимо сравнить со значением максимум2
        если а > максимум 2
          то
            максимум2 = а  //принимаем его в качестве нового значения максимум2
                           // максимум1 в этом случае не меняется
        все
    все
кц

Попробуйте реализовать данный алгоритм самостоятельно.

Пропустить Навигационные Ссылки.
Чтобы оставить комментарий нужна авторизация