Решение задач на C

Здесь находится коллекция решений задач и примеры маленьких программ на языке C.

Первая половина задач и примеров взята из книги Б. Кернигана и Д. Ритчи "Язык программирования C" (второе издание). В отличие от книги задачи либо решены, либо прокомментированы, либо программы дописаны до рабочего состояния.

Вторая половина задач - это ответы на некоторые задания к курсу "Особенности языка C".

В последнем примере "Указатели и массивы" демонстрируются особенности указателей.

K&R (41-43). Вывод самой длиной строки

Решение задач на языке программирования C

В книге в данном разделе опущен момент о том, как происходит обмен данными между функциями (хотя оговаривается перед этим об особенностях передачи массивов в качестве аргументов). Все переменные локальные и поэтому с первого взгляда не понятно, почему функция getline() меняет значение переменной line в функции main(), а copy() - значение longest. Массивы в качестве аргументов передаются не по значению. Переменные в getline() и copy() получают ссылки на массивы, определенные в main(), а не содержимое этих массивов.

#include <stdio.h>
#define MAXLINE 1000
 
/* Не надо использовать getline, иначе будет сообщение о
несовпадении типов. Видимо getline определена в stdio */
int getline2 (char s[], int lim);
void copy(char to[], char from[]);
 
main () {
	int len; // длина текущей строки
	int max; // максимальная длина
	char line[MAXLINE]; // текущая строка
	char longest[MAXLINE]; // самая длиная строка
 
	max = 0; // сначала макс.длина равна нулю
	/* Пока длина строки больше 0 вызывать getline2, передавать
	ей в качестве аргументов массив символов для строки и 
	максимально возможную длину строки. getline2 возвращает
	целое число, которое записывается в len, а также по ходу
	выполнения заполняет массив line. */
	while ((len = getline2(line, MAXLINE)) > 0)
		/* copy будет вызываться только, если длина 
		текущей строки больше значения в max */
		if (len > max) {
			max = len;
			/* copy передается массив символов самой
			длиной строки до этого и текущая строка */ 
			copy (longest, line);
		}
	if (max > 0)
		printf("%s", longest);
	return 0;
}
 
int getline2 (char s[], int lim) {
	int c, i; // символ и счетчик массива
 
	/* Происходит заполнение массива символами текущей строки до тех
	пор, пока не будет превышен лимит, встречен конец файла или 
	конец строки. i - счетчик, который после каждой итерации цикла 
	указывает на следующий элемент массива */
	for (i = 0; i < lim - 1 && (c = getchar()) != EOF && c != '\n'; ++i)
		s[i] = c; // c - это введенный очередной символ
	/* Если цикл for был прерван из-за конца строки, то
	записать символ конца строки в массив. */
	if (c == '\n') {
		s[i] = c;
		++i; // индекс надо увеличить для записи \0
	}
	s[i] = '\0'; // обозначение конца строки в языке Си
	return i; // длина строки
}
 
/* Переменная to связана с longest. Массивы в качестве аргументов
передаются по ссылке, а не по значению. В результате происходит
изменение longest. from связана с line. */
void copy (char to[], char from[]) {
	int i;
 
	i = 0;
	/* Происходит перезапись и дозаполнение  to до тех пор, 
	пока в from не встретится символ конца строки. Перед этим он
	также копируется в to. */
	while ((to[i] = from[i]) != '\0')
		++i;
}

K&R (52-53). Длина строки

Решение задач на языке программирования C

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

В примере ниже строка, вводимая пользователем, записывается в массив символов. Затем ее длина измеряется с помощью встроенной функции strlen(), после чего с помощью пользовательской функции strlen2().

Обращает на себя внимание то, что завершающий символ нуля в строку не записывался, однако видимо он туда автоматически добавляется. Поэтому цикл while в функции strlen2() работает корректно. Тогда непонятно, почему авторы "вручную" дописывают в конец строки нуль в предыдущем примере (поиск самой длиной строки) при считывании ввода.

#include <stdio.h>
#include <string.h>
 
int strlen2 (char s[]);
 
main() {
	int c, i;
	char s[100]; // строка
 
	// Считывание строки
	i = 0;
	while ((c = getchar()) != '\n') {
		s[i] = c;
		++i;
	}
 
	i = strlen(s); // с помощью библиотечной функции
	printf("%d\n", i);
 
	i = strlen2(s); // с помощью собственной функции
	printf("%d\n", i);
}
 
int strlen2 (char s[]) {
	int i;
 
	i = 0;
	while (s[i] != '\0')
		++i;
 
	return i;
}

K&R (61-62). Удаление символов из строки

Решение задач на языке программирования C

Приводится пример функции squeeze, которая удаляет все символы c из строки s.

Ниже представлен полный код программы с использованием этой функции. А также ответ к упражнению 2.4, где предлагается написать функцию, удаляющую из строки s1 все символы, встречающиеся в строке s2.

Алгоритм удаления символа из строки можно описать так:

Другими словами, алгоритм сводится к тому, что символ по индексу i затирается следующим символом, если он совпал с символом для удаления; т.к запись идет по счетчику j, а он увеличивается лишь тогда, когда символы из строки и для удаления не совпадают.

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

Удаление всех символов c из строки

#include <stdio.h>
#define MAX 100
 
void squeeze (char s[], int c);
 
main () {
	char str0[MAX];
	int i, c;
 
	for (i = 0; (c = getchar()) != '\n'; i++) 
		str0[i] = c;
	str0[i] = '\0';
 
	c = getchar();
 
	squeeze (str0, c);
 
	printf("%s\n", str0);
}
 
void squeeze (char s[], int c) {
	int i, j;
 
	for (i = j = 0; s[i] != '\0'; i++)
		if (s[i] != c)
			s[j++] = s[i];
	s[j] = '\0';
}

Удаление всех символов, встречающихся в строке s2, из строки s1

#include <stdio.h>
#define MAX 100
#define DEL 10
 
void squeeze (char s[], char s1[]);
void written (char s[]);
 
main() {
	char str[MAX];
	char str1[DEL];	 	
 
	written (str);
	written (str1);
	squeeze (str, str1);
	printf("%s\n", str);
}
 
void written (char s[100]) {
	int i, c;
 
	i = 0;
	while ((c = getchar()) != '\n') {
		s[i] = c;
		++i;
	}
	s[i] = '\0';
}
 
void squeeze (char s[], char s2[]) {
	int k, i, j;
 
	for (k = 0; s2[k] != '\0'; k++) { 
		for (i = j = 0; s[i] != '\0'; i++)
			if (s[i] != s2[k])
				s[j++] = s[i];
		s[j] = '\0';
	}
}

Примечание. Во второй программе запись символов в строку выделена в отдельную функцию, т.к. надо записать две строки. Иначе пришлось бы дублировать код.

K&R (71-72). Двоичный поиск

Решение задач на языке программирования C

В книге описана функции поиска элемента в упорядоченном массиве с помощью алгоритма двоичного поиска (дихотомии).

Пример рабочей программы с использованием этой функции:

#include <stdio.h>
 
int binsearch (int x, int v[], int n);
 
main () {
	int n = 10;
	int i, k = 2;
	int arr[n];
 
	for (i = 0; i < n; i++) {
		arr[i] = k;
		k += 3;
		printf ("%d ", arr[i]);
	}
 
	printf ("\n");
	scanf ("%i", &k);
 
	i = binsearch (k, arr, n);
	printf("%d\n", i);
}
 
int binsearch (int x, int v[], int n) {
	int low, high, mid;
 
	low = 0;
	high = n - 1;
	while (low <= high) {
		mid = (low + high) / 2;
		if (x < v[mid])
			high = mid - 1;
		else 
			if (x > v[mid])
				low = mid + 1;
			else
				return mid;
	}
	return -1;
}

K&R (73). Замена управляющих символов обычными и наоборот

Решение задач на языке программирования C

Ответ к упражнению 3.2.

Замена управляющих последовательностей обычными символами

#include <stdio.h>
#define MAX 1000
 
void escape (char s[], char s1[]);
 
main () {
	char str[MAX], str1[MAX];
	int i, c;
 
	for (i = 0; (c = getchar()) != EOF; ++i)
		str[i] = c;
 
	escape (str1, str);
	printf("%s\n", str1);	
}
 
void escape (char to[], char from[]) {
	int i, k;
 
	i = k = 0;
	while (from[i] != '\0') {
		switch (from[i]) {
		case '\n':
			to[k++] = '\\';
			to[k++] = 'n';
			break;
		case '\t':
			to[k++] = '\\';
			to[k++] = 't';
			break;
		default:
			to[k++] = from[i];
			break;
		}
		++i;
	}
	to[k] = '\0';
}

Примечание. Используется постфиксная форма инкремента (k++). В этом случае k сначала используется и только потом увеличивается на единицу.
При выводе измененной строки появляются странные "артефакты" в конце.

Замена пар символов "\n" и "\t" управляющими последовательностями

#include <stdio.h>
#define MAX 1000
 
void escape (char s[], char s1[]);
 
main () {
	char str[MAX], str1[MAX];
	int i, c;
 
	for (i = 0; (c = getchar()) != EOF; ++i)
		str[i] = c;
 
	escape (str1, str);
	printf("%s\n", str1);	
}
 
void escape (char to[], char from[]) {
	int i, k;
 
	i = k = 0;
	while (from[i] != '\0') {
		if (from[i] == '\\' && from[i+1] == 'n') {
			to[k++] = '\n';
			i += 2;
		}
		else if (from[i] == '\\' && from[i+1] == 't') {
			to[k++] = '\t';
			i += 2;
		}
		else
			to[k++] = from[i++];
	}
	to[k] = '\0';
}

K&R (77). Функция, разворачивающая строку наподобие a-z

Решение задач на языке программирования C

Ответ к упражнению 3.3. Упрощенная версия.

Программа разворачивает строку наподобие a-z в строку abc...xyz. Если первая строка некорректно записана (например, z-a или oiy), то вторая строка содержит только символ конца строки.

#include <stdio.h>
 
int expand (char s[], char s1[]);
 
main () {
	int i;
	char str[3], str1[50];
 
	i = 0;
	while (i < 3) {
		str[i] = getchar();
		i++;
	}
	str[i] = '\0';
 
	expand(str, str1);
 
	printf("%s\n", str1);
}
 
int expand (char s[], char s1[]) {
	int c1, c2, i;
 
	i = 0;
	if (s[1] == '-' && s[0] < s[2]) {
		c1 = s[0];
		c2 = s[2];
		while (c1 <= c2) {
			s1[i] = c1;
			++i;
			++c1; 
		}
	}
	s1[i] = '\0';
}

K&R (124). Пример использования массива указателей

Решение задач на языке программирования C

Массив months представляет собой массив указателей на первые символы строк. Например, months[3] содержит адрес на символ 'M', который можно получить так: *months[3].

Функция month_name возвращает указатель на первый символ строки. Но как ее получить всю по данному адресу? Ее можно считать в строку (массив символов), инкреминируя указатель, или просто посимвольно вывести на экран. Самый простой способ - это указать формат вывода "строка" (%s) для указателя на первый символ.

#include <stdio.h>
 
char *month_name (int n);
 
main () {
	int m, i;
	char *ch;
	char str[20];
// 1 ---------------------------------------------
	scanf("%d", &m);
	ch = month_name(m);
	i = 0;
	while (*ch != '\0') {
		str[i] = *ch;
		ch++;
		i++;
	}
	str[i] = '\0';
	printf("%s\n", str);
// 2 ---------------------------------------------
	scanf ("%d", &m);
	ch = month_name(m);
	while (*ch != '\0')
		printf("%c", *ch++);
	printf("\n");
// 3 --------------------------------------------
	scanf ("%d", &m);
	ch = month_name(m);
	printf ("%s\n", ch);
}
 
char *month_name (int n) {
	static char *months[] = {
		"Illegal month",
		"January", "February", "March",
		"April", "May", "June",
		"July", "August", "September",
		"October", "November", "December"
	};
 
	return (n < 1 || n > 12) ? months[0] : months[n];
}

Подсчет символов, строк и слов

Решение задач на языке программирования C

Программа считает количество введенных пользователем символов, строк и слов.

#include <stdio.h>
 
main() {
	char ch, flag=-1;
	unsigned c=0, n=0, w=0;
 
	while ((ch = getchar()) != EOF) {
		if (ch == '\n') n++; // строки
		else c++; // символы
 
		if (ch == ' ' || ch == '\n') flag = -1; // слова
		else
			if (flag == -1) {
				flag = 1;
				w++;
			}
	}
 
	printf("%u %u %u\n", c, n, w);
}

Ряд Фибоначчи и вычисление факториала

Решение задач на языке программирования C

Напишите программу, в которой помимо функции main() были бы еще две функции: в одной вычислялся факториал переданного числа, в другой — находился n-ый элемент ряда Фибоначчи (n — параметр функции). Вызовите эти функции с разными аргументами.

#include <stdio.h>
 
unsigned fibonachi (unsigned num);
unsigned long factorial (unsigned n);
 
main () {
     unsigned long result;
 
     result = fibonachi(10);
     printf("Значение 10-го элемента ряда Фибоначчи равно %lu\n", result);
     result = fibonachi(25);
     printf("Значение 25-го элемента ряда Фибоначчи равно %lu\n", result);
 
     result = factorial(5);
     printf("5! = %lu\n", result);
     result = factorial(12);
     printf("12! = %lu\n", result);
}
 
unsigned fibonachi (unsigned num) {
	unsigned i=1, a=0, b=1, s;
 
	while (i++ < num-1) {
		s = a;
		a = b;
		b = s+a;
	}
	return b;
}
 
unsigned long factorial (unsigned n) {
	unsigned long fact=1;
 
	while (n > 0) fact = fact * n--;
 
	return fact;
}

Сравнение дат

Решение задач на языке программирования C

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

#include <stdio.h>
 
main() {
	int dd1, dd2, mm1, mm2, yy1, yy2;
	int i;
 
	printf("Enter first date (dd.mm.yyyy): ");
	scanf("%d.%d.%d", &dd1, &mm1, &yy1);
	printf("Enter second date (dd.mm.yyyy): ");
	scanf("%d.%d.%d", &dd2, &mm2, &yy2);
 
	if (yy1 > yy2) i = 1;
	else 
		if (yy1 < yy2) i = 2;
		else // когда года равны
			if (mm1 > mm2) i = 1;
			else
				if (mm1 < mm2) i = 2;
				else // когда равны года и месяцы
					if (dd1 > dd2) i = 1;
					else 
						if (dd1 < dd2) i = 2;
						else // даты совпадают
							i = 0;
 
	if (i == 1) printf("Первая дата более поздняя\n");
	else 
		if (i == 2) printf("Вторая дата более поздняя\n");
		else printf("Даты совпадают\n");		
}

Функция для объединения строк

Решение задач на языке программирования C

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

void concat (const char *, const char *, char *);
 
main () {
	char str0[50], str1[50], str2[100];
 
	gets(str0);
	gets(str1);
 
	concat(str0, str1, str2);
 
	puts(str2);
}
 
void concat (const char *s0, const char *s1, char *s) {
	int i, j;
 
	for (i=0; s0[i]!='\0'; i++) 
		s[i] = s0[i];
 
	for (j=0; s1[j]!='\0'; j++,i++)
		s[i] = s1[j];
	s[i] = '\0';
}

Соотношение гласных и согласных букв

Решение задач на языке программирования C

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

#include <stdio.h>
#include <string.h>
 
main (int argc, char *argv[]) {
	FILE *f;
	char ch;
	char vowels[] = "aeiouyAEIOUY";
	char cons[] = "bcdfghjklmnpqrstvwxzBCDFGHJKLMNPQRSTVWXZ";
	unsigned v=0, c=0;
 
	f = fopen(argv[1], "r");
 
	if (f == NULL) {
		puts("Не удалось прочитать файл");
		return 1;
	}
 
	while ((ch = getc(f)) != EOF) {
		if (strchr(vowels, ch) != NULL) v++;
		else
			if (strchr(cons, ch) != NULL) c++;
	}
 
	fclose(f);
 
	printf("Гласные: %.2f%%\nСогласные: %.2f%%\n", ((float)v/(v+c))*100, ((float)c/(v+c))*100);	
}

Случайные четные и нечетные числа

Решение задач на языке программирования C

Напишите функцию, которая принимает указатели на два массива. Функция должна заполнять один массив 25-ю случайными четными числами, а другой — 25 нечетными. Продемонстрируйте ее работу.

#include <stdio.h>
#include <time.h>
 
#define N 25
 
void arrs_make(int even[], int odd[]);
void arr_print(int *arr, int n);
 
main () {
	int arr1[N], arr2[N];
 
	arrs_make(arr1, arr2);
 
	arr_print(arr1, N);
	printf("\n");
	arr_print(arr2, N);
	printf("\n");  
}
 
void arrs_make(int *even, int *odd) {
	int i,j,k;
 
	srand(time(NULL));
 
	for (j=0, k=0; j<N || k<N; ) {
		i = rand() % (100) + 250;
		if (i%2 == 0 && j < N) {
			even[j] = i;
			j++;
		} else 
			if (k < N) {
				odd[k] = i;
				k++;
			}
	}
}
 
void arr_print(int *arr, int n) {
	int i;
	for (i=0; i<n; i++)
		printf("%d ", arr[i]);
}

Сохранение динамической структуры в файле

Решение задач на языке программирования C

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

#include <stdio.h>
#include <malloc.h>
#include <string.h>
 
struct site {
       char address[25];
       unsigned index;
       struct site *next;
};
 
struct site *add_site(struct site *, char *adds, int tic); // присоединение элемента к голове, возврат адреса головы
void save(struct site *); // сохранение стека
 
main() {
	char adds[25];
	unsigned tic;
	struct site *head; // адрес, указывающий на голову стека
 
	while (1) {
		head = NULL;
		while (1) {
		   printf("Адрес сайта (s - stop): ");
		   scanf("%s", adds);
		   if (strcmp(adds,"s") == 0) break;
		   printf("Тиц %s: ", adds);
		   scanf("%u", &tic);
		   head = add_site(head,adds,tic);
		}
		printf("\n");
		save(head);
		free(head);
		printf("Продолжить? (y - yes): ");
		scanf("%s",adds);
		if (strcmp(adds,"y") != 0) break;
	}
}
 
struct site *add_site(struct site *head, char *ch, int tic) {
	struct site *element; // указатель на новую структуру		
	element = (struct site *)malloc(sizeof(struct site)); // выделяем память
	element->next = head;
	strcpy(element->address, ch);
	element->index = tic;
	return element;
}
 
void save(struct site *p){
	FILE *f;
	f = fopen("sites.txt","a");
	while (p != NULL) { // пока не конец стека    
	   fprintf(f,"%s - %u\n", p->address, p->index);
	   p = p->next; // продвижение по списку
	}
	fclose(f);
}

Демонстрационный пример. Указатели и массивы

Решение задач на языке программирования C

Этот пример поможет закрепить понимание, как работать с указателем на массив. В выводе программы обратите внимание, адреса различаются между собой на 4 байта, т.е. переменная типа int занимает 4 байта. Также из примера можно удостовериться, что элементы массива располагаются в памяти последовательно друг за другом.

& - операция взятия адреса переменной;
* - операция извлечения значения по указанному адресу; применяется к переменным, содержащим адрес (т.е. к указателям).

Когда переменная-указатель объявляется (например, int *q), перед ее именем также ставится знак *. Однако в данном контексте он просто сообщает, что данная переменная - это указатель, и знак * не имеет отношения к извлечению значения.

#include <stdio.h>
 
main () {
	// объявление массива и его инициализация
	int arr[10] = {101, 102, 103, 104, 105, 106, 107, 108, 109, 110};
	int *p, *q; // указатели на тип int
	int i;
 
	printf("Массив: ");
	for (i = 0; i < 10; i++)
		printf(" [%d]=%d|", i, arr[i]);
	printf("\n\n");
 
// 1 ----------------------------------------------------------------------
	p = &arr[0];
	printf("Адрес 1-го элемента массива (p): %p\n", p);
	printf("Значение 1-го элемента массива (*p): %d\n", *p);
 
	q = p + 1;
	printf("Адрес 2-го элемента массива (q): %p\n", q);
	printf("Значение 2-го элемента массива (*q): %d\n", *q);
 
	q = q + 2;
	printf("Адрес 4-го элемента массива (q): %p\n", q);
	printf("Значение 4-го элемента массива (*q): %d\n", *q);
	printf("\n");
 
// 2 ---------------------------------------------------------------------
	// имя массива является указателем не его первый элемент
	printf("Адрес 1-го элемента массива (arr): %p\n", arr);
	printf("Значение 1-го элемента массива (*arr): %d\n", *arr);
	// Поэтому ...
	p = arr + 2; // то же самое, что p = &arr[0] + 2
	printf("Адрес 3-го элемента массива (arr + 2): %p\n", p);
	printf("Значение 3-го элемента массива (*(arr+2)): %d\n", *p);
	printf("Адрес 6-го элемента массива (p + 3): %p\n", p+3);
	printf("Значение 6-го элемента массива (*(p+3)): %d\n", *(p+3));
	printf("\n");
 
// 3 --------------------------------------------------------------------
	// указатель можно употреблять в выражениях с индексом
	p = arr;
	printf("Значение 10-го элемента массива (p[9]): %d\n", p[9]);
	printf("\n");
 
// 4 --------------------------------------------------------------------
	p = arr; // arr++ использовать нельзя, a p++ можно
	for (i = 0; i < 10; i++, p++)
		printf("%2d-й: %p    %d\n", i+1, p, *p);
}

Вывод программы:

Массив:  [0]=101| [1]=102| [2]=103| [3]=104| [4]=105| [5]=106| [6]=107| [7]=108| [8]=109| [9]=110|

Адрес 1-го элемента массива (p): 0x7fff5c4c0d60
Значение 1-го элемента массива (*p): 101
Адрес 2-го элемента массива (q): 0x7fff5c4c0d64
Значение 2-го элемента массива (*q): 102
Адрес 4-го элемента массива (q): 0x7fff5c4c0d6c
Значение 4-го элемента массива (*q): 104

Адрес 1-го элемента массива (arr): 0x7fff5c4c0d60
Значение 1-го элемента массива (*arr): 101
Адрес 3-го элемента массива (arr + 2): 0x7fff5c4c0d68
Значение 3-го элемента массива (*(arr+2)): 103
Адрес 6-го элемента массива (p + 3): 0x7fff5c4c0d74
Значение 6-го элемента массива (*(p+3)): 106

Значение 10-го элемента массива (p[9]): 110

 1-й: 0x7fff5c4c0d60    101
 2-й: 0x7fff5c4c0d64    102
 3-й: 0x7fff5c4c0d68    103
 4-й: 0x7fff5c4c0d6c    104
 5-й: 0x7fff5c4c0d70    105
 6-й: 0x7fff5c4c0d74    106
 7-й: 0x7fff5c4c0d78    107
 8-й: 0x7fff5c4c0d7c    108
 9-й: 0x7fff5c4c0d80    109
10-й: 0x7fff5c4c0d84    110