Простые программы и алгоритмы. Сюрпризы, советы. Хрестоматия по программированию на Си в Unix

Простые программы и алгоритмы. Сюрпризы, советы.

Составьте программу приветствия с использованием функции printf. По традиции принято печатать фразу "Hello, world !" ("Здравствуй, мир !").

Найдите ошибку в программе

#include <stdio.h>

main(){ printf("Hello, world\n"); }

Ответ: раз не объявлено иначе, функция main считается возвращающей целое значение (int). Но функция main не возвращает ничего - в ней просто нет оператора return.

Корректно было бы так:

#include <stdio.h>

main(){ printf("Hello, world\n"); return 0; }

или

#include <stdio.h>

void main(){ printf("Hello, world\n"); exit(0); }

а уж совсем корректно - так:

#include <stdio.h>

int main(int argc, char *argv[]){ printf("Hello, world\n"); return 0; }

Найдите ошибки в программе

#include studio.h main { int i i := 43 print ('В году i недель') }

Что будет напечатано в приведенном примере, который является частью полной программы:

int n; n = 2; printf ("%d + %d = %d\n", n, n, n + n);

В чем состоят ошибки?

if( x > 2 ) then x = 2; if x < 1 x = 1;

Ответ: в Си нет ключевого слова then, условия в операторах if, while должны браться в ()-скобки.

Напишите программу, печатающую ваше имя, место работы и адрес. В первом варианте программы используйте библиотечную функцию printf, а во втором - puts.

Составьте программу с использованием следующих постфиксных и префиксных операций:

a = b = 5 a + b a++ + b ++a + b --a + b a-- + b

Распечатайте полученные значения и проанализируйте результат.

Цикл for

for(INIT; CONDITION; INCR) BODY

INIT; repeat: if(CONDITION){ BODY; cont: INCR; goto repeat; } out: ;

Цикл while

while(COND) BODY

cont: repeat: if(CONDITION){ BODY; goto repeat; } out: ;

Цикл do

BODY

while(CONDITION) cont: repeat: BODY; if(CONDITION) goto repeat; out: ;

В операторах цикла внутри тела цикла BODY могут присутствовать операторы break и continue; которые означают на наших схемах следующее:

Напишите программу, которая при введении с клавиатуры буквы печатает на терминале ключевое слово, начинающееся с данной буквы. Например, при введении буквы 'b' печатает "break".

Напишите программу, отгадывающую задуманное вами число в пределах от 1 до 200, пользуясь подсказкой с клавиатуры "=" (равно), "<" (меньше) и ">" (больше). Для угадывания числа используйте метод деления пополам.

Напишите программу, печатающую степени двойки

1, 2, 4, 8, ...

Заметьте, что, начиная с некоторого n, результат становится отрицательным из-за переполнения целого.

Напишите подпрограмму вычисления квадратного корня с использованием метода касательных (Ньютона):

x(0) = a 1 a x(n+1) = - * ( ---- + x(n)) 2 x(n)

Итерировать, пока не будет | x(n+1) - x(n) | < 0.001

Внимание! В данной задаче массив не нужен. Достаточно хранить текущее и предыдущее значения x и обновлять их после каждой итерации.

Напишите программу, распечатывающую простые числа до 1000.

1, 2, 3, 5, 7, 11, 13, 17, ... /*#!/bin/cc primes.c -o primes -lm * Простые числа. */ #include <stdio.h>

#include <math.h>

int debug = 0; /* Корень квадратный из числа по методу Ньютона */ #define eps 0.0001 double sqrt (x) double x; { double sq, sqold, EPS; if (x < 0.0) return -1.0; if (x == 0.0) return 0.0; /* может привести к делению на 0 */ EPS = x * eps; sq = x; sqold = x + 30.0; /* != sq */ while (fabs (sq * sq - x) >= EPS) { /* fabs( sq - sqold )>= EPS */ sqold = sq; sq = 0.5 * (sq + x / sq); } return sq; } /* таблица прoстых чисел */ int is_prime (t) register int t; { register int i, up; int not_div; if (t == 2 t == 3 t == 5 t == 7) return 1; /* prime */ if (t % 2 == 0 t == 1) return 0; /* composite */ up = ceil (sqrt ((double) t)) + 1; i = 3; not_div = 1; while (i <= up && not_div) { if (t % i == 0) { if (debug) fprintf (stderr, "%d поделилось на %d\n", t, i); not_div = 0; break; } i += 2; /* * Нет смысла проверять четные, * потому что если делится на 2*n, * то делится и на 2, * а этот случай уже обработан выше. */ } return not_div; } #define COL 6 int n; main (argc, argv) char **argv; { int i, j; int n; if( argc < 2 ){ fprintf( stderr, "Вызов: %s число [-]\n", argv[0] ); exit(1); } i = atoi (argv[1]); /* строка -> целое, ею изображаемое */ if( argc > 2 ) debug = 1; printf ("\t*** Таблица простых чисел от 2 до %d ***\n", i); n = 0; for (j = 1; j <= i; j++) if (is_prime (j)){ /* распечатка в COL колонок */ printf ("%3d%s", j, n == COL-1 ? "\n" : "\t"); if( n == COL-1 ) n = 0; else n++; } printf( "\n---\n" ); exit (0); }

.

В чем ошибка?

файл A.c файл B.c

--------------------------------------------------- extern int x; extern int x; main(){ x=2; f(){ f(); printf("%d\n", x); } }

Ответ: переменная x в обоих файлах объявлена как extern, в результате память для нее нигде не выделена, т.е. x не определена ни в одном файле. Уберите одно из слов extern!

.

В чем ошибка?

файл A.c файл B.c

--------------------------------------------------- int x; extern double x; ... ...

Типы переменных не совпадают. Большинство компиляторов не ловит такую ошибку, т.к. каждый файл компилируется отдельно, независимо от остальных, а при "склейке" файлов в общую выполняемую программу компоновщик знает лишь имена переменных и функций, но не их типы и прототипы. В результате программа нормально скомпилируется и соберется, но результат ее выполнения будет непредсказуем! Поэтому объявления extern тоже полезно выносить в include-файлы:

файл proto.h

----------------- extern int x; файл A.c файл B.c

------------------ ----------------- #include "proto.h" #include "proto.h" int x; ...

то, что переменная x в A.c оказывается описанной и как extern - вполне допустимо, т.к. в момент настоящего объявления этой переменной это слово начнет просто игнорироваться (лишь бы типы в объявлении с extern и без него совпадали - иначе ошибка!).

.

Что печатает программа и почему?

int a = 1; /* пример Bjarne Stroustrup-а */ void f(){ int b = 1; static int c = 1; printf("a=%d b=%d c=%d\n", a++, b++, c++); } void main(){ while(a < 4) f(); }

Ответ:

a=1 b=1 c=1 a=2 b=1 c=2 a=3 b=1 c=3

.

Автоматическая переменная видима только внутри блока, в котором она описана.

Что напечатает программа?

/* файл A.c */ int x=666; /*глоб.*/ main(){ f(3); printf(" ::x = %d\n", x); g(2); g(5); printf(" ::x = %d\n", x); } g(n){ static int x=17; /*видима только в g*/ printf("g::x = %2d g::n = %d\n", x++, n); if(n) g(n-1); else x = 0; } /* файл B.c */ extern x; /*глобал*/ f(n){ /*локал функции*/ x++; /*глобал*/ { int x; /*локал блока*/ x = n+1; /*локал*/ n = 2*x; /*локал*/ } x = n-1; /*глобал*/ }

for(i=0; i < 10; i++) printf(...);

Вспомогательные переменные, не несущие смысловой нагрузки (вроде счетчика повторений цикла, не используемого в самом теле цикла) принято по традиции обозначать однобуквенными именами, вроде i, j. Более того, возможны даже такие курьезы:

main(){ int _ ; for( _ = 0; _ < 10; _++) printf("%d\n", _ ); }

основанные на том, что подчерк в идентификаторах - полноправная буква.

Найдите 2 ошибки в программе:

main(){ int x = 12; printf( "x=%d\n" ); int y; y = 2 * x; printf( "y=%d\n", y ); }

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

Найдите ошибку:

int n; n = 12; main(){ int y; y = n+2; printf( "%d\n", y ); }

Ответ: выполняемый оператор n=12 находится вне тела какой-либо функции. Следует внести его в main() после описания переменной y, либо переписать объявление перед main() в виде

int n = 12;

В последнем случае присваивание переменной n значения 12 выполнит компилятор еще во время компиляции программы, а не сама программа при своем запуске. Точно так же происходит со всеми статическими данными (описанными как static, либо расположенными вне всех функций); причем если их начальное значение не указано явно - то подразумевается 0 ('\0', NULL, ""). Однако нулевые значения не хранятся в скомпилированном выполняемом файле, а требуемая "чистая" память расписывается при старте программы.

По поводу описания переменной с инициализацией:

TYPE x = выражение;

является (почти) эквивалентом для

TYPE x; /* описание */ x = выражение; /* вычисление начального значения */

Рассмотрим пример:

#include <stdio.h>

extern double sqrt(); /* квадратный корень */ double x = 1.17; double s12 = sqrt(12.0); /* #1 */ double y = x * 2.0; /* #2 */ FILE *fp = fopen("out.out", "w"); /* #3 */ main(){ double ss = sqrt(25.0) + x; /* #4 */ ... }

Строки с метками #1, #2 и #3 ошибочны. Почему?

Ответ: при инициализации статических данных (а s12, y и fp таковыми и являются, так как описаны вне какой-либо функции) выражение должно содержать только константы, поскольку оно вычисляется КОМПИЛЯТОРОМ. Поэтому ни использование значений переменных, ни вызовы функций здесь недопустимы (но можно брать адреса от переменных).

В строке #4 мы инициализируем автоматическую переменную ss, т.е. она отводится уже во время выполнения программы. Поэтому выражение для инициализации вычисляется уже не компилятором, а самой программой, что дает нам право использовать переменные, вызовы функций и.т.п., то есть выражения языка Си без ограничений.

Напишите программу, реализующую эхо-печать вводимых символов. Программа должна завершать работу при получении признака EOF. В UNIX при вводе с клавиатуры признак EOF обычно обозначается одновременным нажатием клавиш CTRL и D (CTRL чуть раньше), что в дальнейшем будет обозначаться CTRL/D; а в MS DOS - клавиш CTRL/Z. Используйте getchar() для ввода буквы и putchar() для вывода.

Напишите программу, подсчитывающую число символов поступающих со стандартного ввода. Какие достоинства и недостатки у следующей реализации:

#include <stdio.h>

main(){ double cnt = 0.0; while (getchar() != EOF) ++cnt; printf("%.0f\n", cnt ); }

Ответ: и достоинство и недостаток в том, что счетчик имеет тип double. Достоинство можно подсчитать очень большое число символов; недостаток - операции с double обычно выполняются гораздо медленнее, чем с int и long (до десяти раз), программа будет работать дольше. В повседневных задачах вам вряд ли понадобится иметь счетчик, отличный от long cnt; (печатать его надо по формату "%ld").

Составьте программу перекодировки вводимых символов со стандартного ввода по следующему правилу:

a -> b b -> c c -> d ... z -> a другой символ -> *

Коды строчных латинских букв расположены подряд по возрастанию.

Составьте программу перекодировки вводимых символов со стандартного ввода по следующему правилу:

B -> A C -> B ... Z -> Y другой символ -> *

Коды прописных латинских букв также расположены по возрастанию.

Напишите программу, печатающую номер и код введенного символа в восьмеричном и шестнадцатеричном виде. Заметьте, что если вы наберете на вводе строку символов и нажмете клавишу ENTER, то программа напечатает вам на один символ больше, чем вы набрали. Дело в том, что код клавиши ENTER, завершившей ввод строки - символ '\n' тоже попадает в вашу программу (на экране он отображается как перевод курсора в начало следующей строки!).

Разберитесь, в чем состоит разница между символами '0' (цифра нуль) и '\0' (нулевой байт). Напечатайте

printf( "%d %d %c\n", '\0', '0', '0' );

Поставьте опыт: что печатает программа?

main(){ int c = 060; /* код символа '0' */ printf( "%c %d %o\n", c, c, c); }

Почему печатается 0 48 60? Теперь напишите вместо

int c = 060; строчку

char c = '0';

Что напечатает программа?

#include <stdio.h>

void main(){ printf("ab\0cd\nxyz"); putchar('\n'); }

Запомните, что '\0' служит признаком конца строки в памяти, а '\n' - в файле. Что в строке "abcd\n" на конце неявно уже расположен нулевой байт:

'a','b','c','d','\n','\0'

Что строка "ab\0cd\nxyz" - это

'a','b','\0','c','d','\n','x','y',z','\0'

Что строка "abcd\0" - избыточна, поскольку будет иметь на конце два нулевых байта (что не вредно, но зачем?). Что printf печатает строку до нулевого байта, а не до закрывающей кавычки. Программа эта напечатает ab и перевод строки.

Вопрос: чему равен sizeof("ab\0cd\nxyz")? Ответ: 10.

Напишите программу, печатающую целые числа от 0 до 100.

Напишите программу, печатающую квадраты и кубы целых чисел.

Напишите программу, печатающую сумму квадратов первых n целых чисел.

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

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

Составьте программу ввода двух комплексных чисел в виде A + B * I (каждое на отдельной строке) и печати их произведения в том же виде. Используйте scanf и printf.

Перед тем, как использовать scanf, проверьте себя: что неверно в нижеприведенном операторе?

int x; scanf( "%d", x );

Ответ: должно быть написано "АДРЕС от x", то есть scanf( "%d", &x );

Напишите подпрограмму вычисления корня уравнения f(x)=0 методом деления отрезка пополам. Приведем реализацию этого алгоритма для поиска целочисленного квадратного корня из целого числа (этот алгоритм может использоваться, например, в машинной графике при рисовании дуг):

/* Максимальное unsigned long число */ #define MAXINT (~0L) /* Определим имя-синоним для типа unsigned long */ typedef unsigned long ulong; /* Функция, корень которой мы ищем: */ #define FUNC(x, arg) ((x) * (x) - (arg)) /* тогда x*x - arg = 0 означает x*x = arg, то есть * x = корень_квадратный(arg) */ /* Начальный интервал. Должен выбираться исходя из * особенностей функции FUNC */ #define LEFT_X(arg) 0 #define RIGHT_X(arg) (arg > MAXINT)? MAXINT : (arg/2)+1; /* КОРЕНЬ КВАДРАТНЫЙ, округленный вниз до целого. * Решается по методу деления отрезка пополам: * FUNC(x, arg) = 0; x = ? */ ulong i_sqrt( ulong arg ) { register ulong mid, /* середина интервала */ rgt, /* правый край интервала */ lft; /* левый край интервала */ lft = LEFT_X(arg); rgt = RIGHT_X(arg); do{ mid = (lft + rgt + 1 )/2; /* +1 для ошибок округления при целочисленном делении */ if( FUNC(mid, arg) > 0 ){ if( rgt == mid ) mid--; rgt = mid ; /* приблизить правый край */ } else lft = mid ; /* приблизить левый край */ } while( lft < rgt ); return mid; } void main(){ ulong i; for(i=0; i <= 100; i++) printf("%ld -> %lu\n", i, i_sqrt(i)); }

Использованное нами при объявлении переменных ключевое слово register означает, что переменная является ЧАСТО ИСПОЛЬЗУЕМОЙ, и компилятор должен попытаться разместить ее на регистре процессора, а не в стеке (за счет чего увеличится скорость обращения к этой переменной). Это слово используется как

register тип переменная; register переменная; /* подразумевается тип int */

От регистровых переменных нельзя брать адрес: &переменная ошибочно.

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

C(0,n) = C(n,n) = 1 n = 0... C(k,n+1) = C(k-1,n) + C(k,n) k = 1..n n - номер строки

В разных вариантах используйте циклы, рекурсию.

Напишите функцию вычисления определенного интеграла методом Монте-Карло. Для этого вам придется написать генератор случайных чисел. Си предоставляет стандартный датчик ЦЕЛЫХ равномерно распределенных псевдослучайных чисел: если вы хотите получить целое число из интервала [A..B], используйте

int x = A + rand() % (B+1-A);

Чтобы получать разные последовательности следует задавать некий начальный параметр последовательности (это называется "рандомизация") при помощи

srand( число ); /* лучше нечетное */

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

srand(NBEG); x=rand(); ... ; x=rand(); /* и повторить все сначала */ srand(NBEG); x=rand(); ... ; x=rand();

Используемый метод получения случайных чисел таков:

static unsigned long int next = 1L; int rand(){ next = next * 1103515245 + 12345; return ((unsigned int)(next/65536) % 32768); } void srand(seed) unsigned int seed; { next = seed; }

Для рандомизации часто пользуются таким приемом:

char t[sizeof(long)]; time(t); srand(t[0] + t[1] + t[2] + t[3] + getpid());

Напишите функцию вычисления определенного интеграла по методу Симпсона.

/*#!/bin/cc $* -lm * Вычисление интеграла по методу Симпсона */ #include <math.h>

extern double integral(), sin(), fabs(); #define PI 3.141593 double myf(x) double x; { return sin(x / 2.0); } int niter; /* номер итерации */ void main(){ double integral(); printf("%g\n", integral(0.0, PI, myf, 0.000000001)); /* Заметьте, что myf, а не myf(). * Точное значение интеграла равно 2.0 */ printf("%d итераций\n", niter ); } double integral(a, b, f, eps) double a, b; /* концы отрезка */ double eps; /* требуемая точность */ double (*f)(); /* подынтегральная функция */ { register long i; double fab = (*f)(a) + (*f)(b); /* сумма на краях */ double h, h2; /* шаг и удвоенный шаг */ long n, n2; /* число точек разбиения и оно же удвоенное */ double Sodd, Seven; /* сумма значений f в нечетных и в четных точках */ double S, Sprev;/* значение интеграла на данной и на предыдущей итерациях */ double x; /* текущая абсцисса */ niter = 0; n = 10L; /* четное число */ n2 = n * 2; h = fabs(b - a) / n2; h2 = h * 2.0; /* Вычисляем первое приближение */ /* Сумма по нечетным точкам: */ for( Sodd = 0.0, x = a+h, i = 0; i < n; i++, x += h2 ) Sodd += (*f)(x); /* Сумма по четным точкам: */ for( Seven = 0.0, x = a+h2, i = 0; i < n-1; i++, x += h2 ) Seven += f(x); /* Предварительное значение интеграла: */ S = h / 3.0 * (fab + 4.0 * Sodd + 2.0 * Seven ); do{ niter++; Sprev = S; /* Вычисляем интеграл с половинным шагом */ h2 = h; h /= 2.0; if( h == 0.0 ) break; /* потеря значимости */ n = n2; n2 *= 2; Seven = Seven + Sodd; /* Вычисляем сумму по новым точкам: */ for( Sodd = 0.0, x = a+h, i = 0; i < n; i++, x += h2 ) Sodd += (*f)(x); /* Значение интеграла */ S = h / 3.0 * (fab + 4.0 * Sodd + 2.0 * Seven ); } while( niter < 31 && fabs(S - Sprev) / 15.0 >= eps ); /* Используем условие Рунге для окончания итераций */ return ( 16.0 * S - Sprev ) / 15.0 ; /* Возвращаем уточненное по Ричардсону значение */ }

Где ошибка?

struct time_now{ int hour, min, sec; } X = { 13, 08, 00 }; /* 13 часов 08 минут 00 сек.*/

Ответ: 08 - восьмеричное число (так как начинается с нуля)! А в восьмеричных числах цифры 8 и 9 не бывают.

Дан текст:

int i = -2; i <<= 2; printf("%d\n", i); /* печать сдвинутого i : -8 */ i >>= 2; printf("%d\n", i); /* печатается -2 */

Закомментируем две строки (исключая их из программы):

int i = -2; i <<= 2; /* printf("%d\n", i); /* печать сдвинутого i : -8 */ i >>= 2; */ printf("%d\n", i); /* печатается -2 */

Почему теперь возникает ошибка? Указание: где кончается комментарий?

Ответ: Си не допускает вложенных комментариев. Вместо этого часто используются конструкции вроде:

#ifdef COMMENT ... закомментированный текст ... #endif /*COMMENT*/

и вроде

/**/ printf("here");/* отладочная выдача включена */ /* printf("here");/* отладочная выдача выключена */

или

/* выключено(); /**/ включено(); /**/

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

/*printf("here"); */

Почему программа печатает неверное значение для i2 ?

int main(int argc, char *argv[]){ int i1, i2; i1 = 1; /* Инициализируем i1 / i2 = 2; /* Инициализируем i2 */ printf("Numbers %d %d\n", i1, i2); return(0); }

Ответ: в первом операторе присваивания не закрыт комментарий - весь второй оператор присваивания полностью проигнорировался! Правильный вариант:

int main(int argc, char *argv[]){ int i1, i2; i1 = 1; /* Инициализируем i1 */ i2 = 2; /* Инициализируем i2 */ printf("Numbers %d %d\n", i1, i2); return(0); }

А вот "шальной" комментарий.

void main(){ int n = 10; int *ptr = &n; int x, y = 40; x = y/*ptr /* должно быть 4 */ + 1; printf( "%d\n", x ); /* пять */ exit(0); } /* или такой пример из жизни - взят из переписки в Relcom */ ... cost = nRecords/*pFactor /* divided by Factor, and */ + fixMargin; /* plus the precalculated */ ...

Результат непредсказуем. Дело в том, что y/*ptr превратилось в начало комментария!

Поэтому бинарные операции принято окружать пробелами.

x = y / *ptr /* должно быть 4 */ + 1;

Найдите ошибки в директивах препроцессора Си (вертикальная черта обозначает левый край файла).

| | #include <stdio.h>

|#include < sys/types.h >

|# define inc (x) ((x) + 1) |#define N 12; |#define X -2 | |... printf( "n=%d\n", N ); |... p = 4-X;

Ответ: в первой директиве стоит пробел перед #. Диез должен находиться в первой позиции строки. Во второй директиве в <> находятся лишние пробелы, не относящиеся к имени файла - препроцессор не найдет такого файла! В данном случае "красота" пошла во вред делу. В третьей - между именем макро inc и его аргументом в круглых скобках (x) стоит пробел, который изменяет весь смысл макроопределения: вместо макроса с параметром inc(x) мы получаем, что слово inc будет заменяться на (x)((x)+1). Заметим однако, что пробелы после # перед именем директивы вполне допустимы. В четвертом случае показана характерная опечатка - символ ; после определения. В результате написанный printf() заменится на

printf( "n=%d\n", 12; );

где лишняя ; даст синтаксическую ошибку.

В пятом случае ошибки нет, но нас ожидает неприятность в строке p=4-X; которая расширится в строку p=4--2; являющуюся синтаксически неверной. Чтобы избежать подобной ситуации, следовало бы написать

p = 4 - X; /* через пробелы */

но еще проще (и лучше) взять макроопределение в скобки:

#define X (-2)

Напишите функцию max(x, y), возвращающую большее из двух значений. Напишите аналогичное макроопределение. Напишите макроопределения min(x, y) и abs(x) (abs модуль числа). Ответ:

#define abs(x) ((x) < 0 ? -(x) : (x)) #define min(x,y) (((x) < (y)) ? (x) : (y))

Зачем x взят в круглые скобки (x)? Предположим, что мы написали

#define abs(x) (x < 0 ? -x : x ) вызываем abs(-z) abs(a|b) получаем (-z < 0 ? --z : -z ) (a|b < 0 ? -a|b : a|b )

Содержание раздела