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

1.30.

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

1.31.

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

1.32.

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

            1, 2, 4, 8, ...

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

1.33.

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

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

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

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

1.34.

Напишите программу, распечатывающую простые числа до 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);
    }

1.35.

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

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

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

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

1.36.

Напишите подпрограмму вычисления корня уравнения 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 */

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

1.37.

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

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

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

1.38.

Напишите функцию вычисления определенного интеграла методом Монте-Карло. Для этого вам придется написать генератор случайных чисел. Си предоставляет стандартный датчик ЦЕЛЫХ равномерно распределенных псевдослучайных чисел: если вы хотите получить целое число из интервала [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());

1.39.

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

    /*#!/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 ;
            /* Возвращаем уточненное по Ричардсону значение */
    }

1.40.

Где ошибка?

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

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

1.41.

Дан текст:

       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");
        */

1.42.

Почему программа печатает неверное значение для 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);
    }

1.43.

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

    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;

1.44.

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

            |
            | #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)

1.45.

Напишите функцию 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 )

У нас появилась "дикая" операция --z; а выражение a|b<0 соответствует a|(b<0), с совсем другим порядком операций! Поэтому заключение всех аргументов макроса в его теле в круглые скобки позволяет избежать многих неожиданных проблем. Придерживайтесь этого правила!

Вот пример, показывающий зачем полезно брать в скобки все определение:

    #define div(x, y)     (x)/(y)

При вызове

         z = sizeof div(1, 2);
             превратится в
         z = sizeof(1) / (2);

что равно sizeof(int)/2, а не sizeof(int). Вариант

    #define div(x, y) ((x) / (y))

будет работать правильно.

1.46.

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

    int sqr(int x){ return x  *  x; }
    #define SQR(x)       ((x) * (x))
    main(){ int y=2, z;
       z = sqr(y++); printf("y=%d z=%d\n", y, z);
       y = 2;
       z = SQR(y++); printf("y=%d z=%d\n", y, z);
    }

Вызов функции sqr печатает "y=3 z=4", как мы и ожидали. Макрос же SQR расширяется в

       z = ((y++) * (y++));

и результатом будет "y=4 z=6", где z совсем не похоже на квадрат числа 2.

1.47. ANSI

ANSI препроцессор^** языка Си имеет оператор ## - "склейка лексем":

    #define VAR(a, b)       a ## b
    #define CV(x)           command_ ## x
    main(){
      int VAR(x, 31) = 1;
      /* превратится в int x31 = 1; */
      int CV(a) = 2; /* даст int command_a = 2; */
      ...
    }

Старые версии препроцессора не обрабатывают такой оператор, поэтому раньше использовался такой трюк:

    #define VAR(a, b)       a/**/b

в котором предполагается, что препроцессор удаляет комментарии из текста, не заменяя их на пробелы. Это не всегда так, поэтому такая конструкция не мобильна и пользоваться ею не рекомендуется.

1.48.

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

    #include <stdio.h>
    main(){
      int max, min, x, n;
      for( n=0; scanf("%d", &x) != EOF; n++)
            if( n == 0 ) min = max = x;
            else{
               if( x > max ) max = x;
               if( x < min ) min = x;
            }
      printf( "Ввели %d чисел: min=%d max=%d\n",
                     n,            min,   max);
    }

Напишите аналогичную программу для поиска максимума и минимума среди элементов массива, изначально min=max=array[0];

1.49.

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

    /*
     * Сортировка по методу Шелла.
     * Сортировке подвергается массив указателей на данные типа obj.
     *      v------.-------.------.-------.------0
     *             !       !      !       !
     *             *       *      *       *
     *            элементы типа obj
     * Программа взята из книги Кернигана и Ритчи.
     */
    #include <stdio.h>
    #include <string.h>
    #include <locale.h>
    #define obj char
    static shsort (v,n,compare)
    int n;              /* длина массива */
    obj *v[];           /* массив указателей */
    int (*compare)();   /* функция сравнения соседних элементов */
    {
            int g,      /* расстояние, на котором происходит сравнение */
                i,j;    /* индексы сравниваемых элементов */
            obj *temp;
            for( g = n/2 ; g > 0  ; g /= 2 )
            for( i = g   ; i < n  ; i++    )
            for( j = i-g ; j >= 0 ; j -= g )
            {
                    if((*compare)(v[j],v[j+g]) <= 0)
                        break;      /* уже в правильном порядке */
                    /* обменять указатели */
                    temp = v[j]; v[j] = v[j+g]; v[j+g] = temp;
                    /* В качестве упражнения можете написать
                     * при помощи curses-а программу,
                     * визуализирующую процесс сортировки:
                     * например, изображающую эту перестановку
                     * элементов массива */
            }
    }
    /* сортировка строк */
    ssort(v) obj **v;
    {
            extern less();  /* функция сравнения строк */
            int len;
            /* подсчет числа строк */
            len=0;
            while(v[len]) len++;
            shsort(v,len,less);
    }
    /* Функция сравнения строк.
     * Вернуть целое меньше нуля, если a <  b
     *                      ноль, если a == b
     *               больше нуля, если a >  b
     */
    less(a,b) obj *a,*b;
    {
            return strcoll(a,b);
            /* strcoll - аналог strcmp,
             * но с учетом алфавитного порядка букв.
             */
    }
    char *strings[] = {
            "Яша", "Федя", "Коля",
            "Гриша", "Сережа", "Миша",
            "Андрей Иванович", "Васька",
            NULL
    };
    int main(){
            char **next;
            setlocale(LC_ALL, "");
            ssort( strings );
            /* распечатка */
            for( next = strings ; *next ; next++ )
                    printf( "%s\n", *next );
            return 0;
    }

^* Препроцессор Си - это программа /lib/cpp

^** ANSI - American National Standards Institute, разработавший стандарт на язык Си и его окружение.

Назад | Содержание | Вперед