Ликбез по контрольной работе №1

likbez_1

!По результатам доп. занятия. 
printf и вообще форматный I/O: http://www.cplusplus.com/reference/cstdio/printf/
Прошу прощения за неверный комментарий относительно беззнакового модификатора - глаз "замылился" - просто %u (смотрите man, там исчерпывающая информация).
Относительно рекурсии - как писать рекурсию и как сводить задачи от рекурсии к ДП по массиву, вроде бы , разобрались.
Демонстрирую (чтобы не забывали + по желанию учащихся):
Написать рекурсивную функцию, проверяющую, является ли число n степенью 2-х:
int recursion(double n) {
        // Условие остановки: мы делили/делили наше число на два, в итоге получили 1
        if (n == 1) {
            printf("YES\n");
        } 
        // Условие остановки:мы делили/делили наше число на два, в итоге получили дробное число
        else if (n > 1 && n < 2) {
            printf("NO\n");
        }
        else { //иначе - рекурсивный спуск , и аргумент на этом шаге делим на два
            return recursion(n / 2);
        }
}

с ф-ями тоже разобрались. Всё же.
void a() { 
....
        return;
}

int b() {
        int res; // - это уже другая res, локальная в b
.....
        return res;
}

int main() {
int res; 
.....
a(); // на этом этапе компилятор должен знать, что такое a(). Не хотите описывать сверху - пишите прототип void a();
res = b();
......
return 0;
}

Далее по функциям - модификатор static для локального контекста - (экстракт из свойств, который вам может быть полезен на контесте)
расширяем время жизни на всё время жизни программы, оставляя область видимости - внутри ф-и. Инициализируется нулем.

то есть. 
Пусть у вас счетчик i и ф-я

int inc() {
        static int i;
        i++;
        return i;
}

Трижды вызвав inc(), получите 3 в i; 
не расширяя области видимости

бонус: решето Эратосфена (по желаниям учащихся):
http://www.alexeypetrov.narod.ru/C/simple_about.html
_____________________________________________________________________________________________________________________
0) Условный оператор. Здесь всё просто, главное - формализовать задачу в Си-коде. 
Могут понадобиться математические ф-и и константы. 
На всякий случай, сопровождаю вышесказанное примером вычисления арккосинуса и синуса двух чисел:

#include <stdio.h>
#include <math.h>

int main() {
        printf("%f\n", acos(1));
        printf("%f\n", sin(M_PI)); //M_PI - константа из math.h
return 0;
}
собирать с флагом -lm (при отладке, на системе соберется с ним автоматически).

Примеры 2015 г.: 
а) два вещественных числа x,y - стороны прямоугольного треугольника, одна из сторон является гипотенузой.
Найдите тангенс меньшего угла треугольника.
В данной задаче также полезно помнить формат вывода для точности вещественного числа.
б) найти наименьший по модулю корень кубического уравнения. Эта задача - "на подумать" о методах, которыми Вы пользовались
(теоретически) в школе. См. формулы Кардано, пример 3:
http://math.intemodino.com/ru/algebra/equations/cardano's-formula-for-solving-cubic-equations.html
Или формулы Виета для кубического уравнения.
Может пригодиться.

А, если бы я забыл вообще всё, да так затупил, что не узнал бы "в бою", я бы решал эту задачу прогонкой - некоторые тесты она уж точно прошла бы. 
На остальных - Timelimit или #взависимостиоттогокаквынаписали:)
Выделил бы EPS(тут оно равно 1) #define EPS 1, к примеру, и пошел бы от нуля в обе стороны. 
_____________________________________________________________________________________________________________________
1) Работа со строками. Типичные случаи.
a) считать последовательность символов неограниченной длины.
Будем использовать ф-ю 'int getchar()', возвращающую код считанного символа.

int с;
while ( (с=getchar()) != EOF ) {
//Делаем то, что нужно со считанным символом.
//Например, кастуем его к (char) и записываем в соответствующий элемент массива
}

б) задачи стандартные: записать что-то , посчитать, проверить очень длинное число на делимость.
__________________________________________________________________________________________________________________________
2) Двумерные массивы.
Для работы с двумерными массивами нам нужно:
а) знать , как задавать (пока что статически) массивы в Си.
б) знать циклы (например for) и уметь писать вложенные циклы.
Демонстрируется обход двумерного массива (пусть в нём каждому элементу присваивается 1).

define N 100;
int a[N][N];
int i,j;
...
for(i=0;i<N;i++) {
  for(j=0;j<N;j++) { //несмотря на то, что границы блоков для однострочной операции указывать необязательно, я пока что требую это от вас для порядка 
    a[i][j] = 1;
  }
}

В прошлом году была задача на возведение матрицы в степень двойки. В одной из презентаций мы упоминали быстрое возведение в степень двойки для числа. 
Для матрицы тот же принцип. "Как?" - спросите Вы. А вот:
Мы проходили и как перемножить матрицы, и как устроить рекурсию, и как решать итеративно.
Я бы её решал так: разложил степень 2^n на 2*2*...*2 и провёл бы рекурсию. Ну либо безрекурсивное ДП по матрице, что ещё лучше. 
То есть для матрицы M и n=3 это перемножение матриц ( _M^4_ * M^4 ) = ( ( _M^2_ * M^2 ) * ( M^2 * M^2 ) ) = (_M * M_ * M * M * M * M * M * M) = _M^8_
Учтите здесь симметрию и улучшите результат в O(log(n)) раз! (Я даже _подчеркнул_!)
__________________________________________________________________________________________________________________________
3) Функции.
Здесь всё просто. Главное - то, что эта функция будет делать и что возвращать.
Пример - 2015:
Напишите функцию, которая считает то, что спрашивают в пункте "0)а)". 
И дан прототип:
double trig(double a, double b);
^                   ^
|                   |
возвращаемый тип  аргументы с типами
                   через зпт.
                   
Так и пишем:
double trig(double a, double b) {
  double res;
 /* Что-то делаем, результат записываем в res 
  return res;
}

________________________________________________________________________________________________________

Вместо послесловия - будьте внимательны!
Если в задаче пишут формат вывода такой-то, то проверять 10 раз, соответствует ли Ваш вывод формату.
Если пишут , что на ввод подаются числа, меньшие 2^63 по модулю, то используйте long int, а не int. 
Надеюсь, это всем понятно :) Иначе не пущу на контест :)
Если пишут: вывести число с точностью до 5 знаков после запятой, то и пишите %.5f или %.5lf...
Опять-таки, приведение типов. Вспоминайте правила с 1-го семинара. Ниже по ссылке есть всё :)
http://acm.mipt.ru/twiki/pub/Cintro/ForPreps/c_2_basic.pdf