Раздел «Язык Си».CIntroTasks1:

Задачи контрольной по технике программирования на языке Си. Требования к знаниям языка Си - базовый уровень.

Теоретические вопросы

Содержание

Основы работы с файлами и с компилятором

Язык Си

Общие замечания

Здесь приведён примерный список тем задач. Каждую задачу можно оформить в нескольких вариантах, с указанием (по возможности)

Следует использовать стандартные потоки ввода и вывода для считывания и вывода данных.

В каждой задаче присутствует дополнительные вопросы:

Ответы на теоретические вопросы должны быть даны в комментариях в начале текстов программ.

Список задач на acm.mipt.ru/judge

Другие задачи

Задачи на технику

Инвертирование строки.


Архимедовы тройки. Найдите все тройки натуральных чисел (a, b, c), такие что 0 < a \le b \le c \le N и a^2+b^2=c^2.


Перевёртывание строки.


Выведите все четырёхзначные числа, сумма цифр которых равна заданному числу N.


Таблица умножения. Напишите программу, которая считывает N и выводит таблицу умножения N x N.


Пересечение множеств. Напишите программу, которая находит пересечение двух введенных множеств целых чисел.


Сумма квадратов. Напишите программу, которая находит сумму квадратов первых N натуральных чисел.


Напишите программу, которая находит частичную сумму ряда a_n = 1/n^2.


Напишите программу, которая выводит все бинарные слова длины N.


Напишите программу, которая выводит все бинарные слова длины N, в которых ровно K единиц


Напишите программу, которая считывает N натуральных чисел, и выводит их в том же порядке, исключив нечётные числа.


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


Напишите программу, которая считывает из стандартного потока символы, и печатает их на стандартный поток вывода, и при этом

Программа должна заканчивать свою работу при достижении конца потока (EOF).


Напишите программу, которая считывает символы из стандартного потока ввода и при достижении конца потока печатает число встретившихся


Напишите функцию int word_to_int(char *s), которая строку символов пытается интерпретировать как целое число и возвращает значение этого целого числа. Если запись целого числа некорректна, то функция должна возвращать 0. Функции scanf и atoi изпользовать нельзя.


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


Напишите программу, которая считывает символы из станларного потока ввода и при достижении конца ввода (EOF) выводит количество встретившихся символов '\n'.


Напишите программу, которая считывает символы из стандартного потока ввода и при достижении конца ввода печатает частоты встретившихся символов.

НОД, НОК, делимость

НОД. Напишите функцию НОД: long gcd(long, long).


НОК. Напишите функцию НОК: long lcd(long, long).


Делители. Напишите программу, которая выводит все делители введённого числа.


Функция Эйлера. Для данного числа N найдите число f(N) взаимопростых с ним чисел из множества {1, ..., n-1}.


Простое число. На вход поступает натуральное число менее 2^31. Выведите ДА или НЕТ, в зависимости от того, простое оно или нет.


Решето Эратосфена. На вход поступает натуральное число N менее 2^31. Выведите все простые числа от 1 до N. Используйте для этого алгоритм Эратосфена, описанный в учебнике в первом семинаре.

Задачи на вычисление последовательностей и треугольников

Числа Фибоначчи 1. Напишите реализацию итеративного алгоритма вычисления чисел Фибоначчи.


Числа Фибоначчи 2. Напишите реализацию рекурсивного алгоритма вычисления чисел Фибоначчи.


Числа Фибоначчи 3. Найдите последнее число Фибоначчи, представимое типом long. Напишите для этого программу.


Числа Фибоначчи 4 (сложная). Напишите программу, вычисляющую все числа Фибоначчи от f(0) до f(1000).


Треугольник Паскаля 1. Треугольник Паскаля сотоит из чисел, каждое из которых равно сумме двух чисел, стоящих над ним в предыдущей строчке. На сторонах треугольника стоят единицы:

                 1
               1   1
             1   2   1
           1   3   3   1
         1   4   6   4   1
       1   5   10  10   5  1
              ..    ..
Напишите программу, которая вычисляет N-ю строчку треугольника Паскаля.


Треугольник Паскаля 2. Обозначим числа в треугольника Паскаля как C(n,k), где n - номер строки, k - номер числа слева. Нумерация n и k начинается с 0. Напишите рекурсивный алгоритм вычисления чисел C(n,k). Оцените как растет время вычисления C(2n,n) с ростом n.


Степень. Напишите рекурсивную функцию double power(double x, int n), которая вычисляет f(x,n)=x^n согласно рекуррентной формуле: x^n=

Напишите программу, которая в цикле запрашивает пару чисел x и n (раделенных пробельными символами), а выводит результат x^n и число вызовов функции power, которые были сделаны во время вычислений. Программа должна завершать свою работу, если пользователь введёт что-нибудь отличное от пары чисел, соответствующих форматам "%lf" и "%d" функции scanf.

Задачи на системы счисления

B2_to_B10. Напишите программу, которая переводит числа из двоичной системы в десятичную


B10_to_B2. Напишите программу, которая переводит числа из десятичной в двоичную.


Число единиц. Напишите программу, которая определяет число единиц в двоичной записи введенного числа


Сумма степеней двойки. Напишите программу, которая для данного натурального числа N предъявляет его разложение на сумму неповторяющихся степеней двойки.


Сумма степеней тройки. Напишите программу, которая для данного натурального числа N предъявляет его разложение на сумму неповторяющихся степеней тройки, взятых со знаком + или -.


B16_to_B8. Напишите программу, которая для данного 16-чного представления натурального числа выводит его 8-чное представление.


B8_to_B16. Напишите программу, которая для данного 8-чного представления натурального числа выводит его 16-чное представление.


B2_to_B16. Напишите программу, которая для данного 2-чного представления натурального числа выводит его 16-чное представление.


Сумма чисел в двоичной системе. Напишите программу для сложения двух больших натуральных чисел, заданных в двоичной системе счисления.


Задачи на генерацию случайных чисел

Сгенерируйте N случайных натуральных чисел из диапазона [A,B].


Сгенерируйте случайную N перестановку первых N натуральных чисел.


Напишите генератор случайных точек из круга X^2+Y^2<1.

Задачи на типы языка Си

Предъявите внутреннее представление числа 0.00175 типом double. Напишите для этого программу, которая выводит биты переменной double x=0.00175L.


Предъявите внутреннее представление числа -177 типом int. Напишите для этого программу, которая выводит биты переменной int x=-177.


Напишите программу, при выполнении которой происходит переполнение при операции над типом а) double; б) int.


Найдите самую большую степень тройки, представимую типом long. Напишите программу, которая находит это число, и по коду которой можно судить о правильности ответа.


(*) Найдите самую большую степень тройки, которая абсолютно точно представима типом double. Напишите программу, которая находит это число, и по коду которой можно судить о правильности ответа.


Выведите символы, у которых ASCII коды равны 50, 51, ...., 127.

Неотклассифицированные задачи

Напишите программу, которая решает квадратное уравнение.


На вход поступает сначала число N, а затем N целых чисел менее 2000000.

Форматы входа и выхода:


Напишите программу, которая определяет правильность введённой скобочной структуры (PROB:008). При решении задачи нельзя использовать массивы.

Info.CommonWebForm
Type: Другое
Stuff: Other
Date:  
ID:  
Importance: Medium
Author: Ворожцов Артем
Summary:  

Attachment sort Action Size Date Who Comment down
solutions.zip manage 12.5 K 22 Nov 2006 - 20:34 ArtemVoroztsov Решения задач контрольной
test1.pdf manage 194.2 K 22 Nov 2006 - 20:48 ArtemVoroztsov Задачи контрольной