Язык Си в примерах/Таблица умножения

Материал из Викиучебника — открытых книг для открытого мира
Перейти к: навигация, поиск

Язык Си в примерах


  1. Компиляция программ
  2. Простейшая программа «Hello World»
  3. Учимся складывать
  4. Максимум
  5. Таблица умножения
  6. ASCII коды символов
  7. Верхний регистр
  8. Скобочки
  9. Факториал
  10. Степень числа
  11. Треугольник Паскаля
  12. Корень уравнения
  13. Система счисления
  14. Сортировка
  15. Библиотека complex
  16. Сортировка на основе qsort
  17. RPN калькулятор
  18. RPN калькулятор на Bison
  19. Простая грамматика
  20. Задача «Расчёт сопротивления схемы»
  21. Простая реализация конечного автомата
  22. Использование аргументов командной строки
  23. Чтение и печать без использования stdio
  24. Декодирование звукозаписи в формате ADX
Дано
положительное целое число n (в «текстовом» десятичном представлении), переданное программе как аргумент командной строки. Значение n2 не превышает максимального допустимого значения для типа long (LONG_MAX.)
Надо
вывести на стандартный вывод таблицу умножения размера n × n.
Указания
  • Начать разработку программы можно с цикла (j = 1, …, n) вывода некоторой (i-ой) строки таблицы. Затем, этот цикл (цикл значений) можно в свою очередь заключить в цикл строк (i = 1, …, n.)
  • Для выравнивания столбцов таблицы имеет смысл воспользоваться формулой длины десятичного представления положительного целого числа (x ⩾ 0) — w = 1 + ⌊lg (x)⌋ = ⌈lg (1 + x)⌉ (где ⌊α⌋ и ⌈α⌉ — операции округления «к нулю» и «от нуля», соответственно.)
Дополнительно
включите в программу интерпретацию аргумента (n) согласно правилам языка Си для числовых констант. Реализуйте вывод таблицы умножения в шестнадцатеричном, восьмеричном или десятичном представлении в зависимости от способа записи аргумента командной строки. (Так, например, аргумент 0x12 должен приводить к выводу таблицы умножения 18 × 18 в шестнадцатеричном представлении.)
Новые элементы языка
форма записи символьных констант; операторы continue, for; функции ceil, isdigit, log, putchar, strchr, strtol; указатель разрядности * форматного преобразования; двуаргументная форма объявления функции main.

Решение[править]

#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>

int
main (int argc, char *argv[])
{
  assert (argc - 1 == 1);
  long n;
  {
    char *tail;
    n = strtol (argv[1], &tail, 0);
    assert (tail > argv[1]);
    assert (*tail == '\0');
  }

  assert (n >= 1);
  assert (n <= sqrt (LONG_MAX));
  const int width = (int)ceil (2 * log (1 + n) / log (10));

  long i;
  for (i = 1; i <= n; i++) {
    long j;
    for (j = 1; j <= n; j++) {
      printf (" %*ld", width, i * j);
    }
    putchar ('\n');
  }

  return 0;
}

Примета работы программы (построение таблицы умножения для n = 5):

$ ./multable 5 
  1  2  3  4  5
  2  4  6  8 10
  3  6  9 12 15
  4  8 12 16 20
  5 10 15 20 25
$ 

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

Цикл строк[править]

В данном примере мы используем оператор цикла for, являющийся обобщением уже рассмотренного нами в разделе Максимум оператора while.[1] А именно, запись while (выражение) тело равносильна for (; выражение; ) тело. С другой стороны, цикл строк в примере выше можно было бы записать с использованием while следующим образом:

  long i = 1;
  while (i <= n) {
    код-вывода-строки;
    i++;
  }

Иными словами, для первой итерации цикла мы присваиваем переменной i значение 1. Затем, мы выводим очередную (i-ую) строку пока i не превысит заданного пользователем значения n. Завершает тело цикла инкремент (увеличение на 1) номера строки i.

С точки зрения языка, содержимое «скобок» оператора for состоит из трех разделенных точкой с запятой (;) частей, каждая из которых может быть или пустой, или совершенно произвольным выражением; например: i = 1, f (42), x *= 3, a = b = c. При этом:

  1. первое выражение — инициализация — вычисляется перед началом цикла, — как если бы было записано непосредственно перед самим оператором for;
  2. второе выражение — условие — вычисляется перед каждой итерацией, — совершенно аналогично условию для оператора while;
  3. наконец, третье выражение — изменение — выполняется в конце («после») каждой итерации.

Можно было бы сказать, что оператор for является избыточным при наличии while, однако в языке существует также оператор continue, досрочно завершающий текущую итерацию[2] (с переходом к проверке условия и, при его выполнении, — к следующей итерации.) При использовании while, выражение «изменения» («перехода к следующей итерации») пришлось бы дублировать возможно перед каждым случаем использования оператора continue. Напротив, в случае for, выражение изменения выполняется после любой итерации — даже если таковая завершена досрочно.

Цикл значений[править]

Телом цикла строк должна стать, очевидно, некая процедура вывода заданной строки, которую мы вновь оформляем как цикл — использующий уже новую переменную j:

    long j;
    for (j = 1; j <= n; j++) {
      printf (" %*ld", width, i * j);
    }
    putchar ('\n');

В данном коде, мы встречаемся с двумя новыми возможностями языка. Первая из них — указатель * переменной разрядности преобразования в строке формата функции printf.[3] В данном случае, наличие этого указателя (в форме %*ld) означает, что вместо одного аргумента, функция printf использует для форматного преобразования два (а именно: width и произведение i × j.) При этом, первый аргумент задает разрядность преобразования, второй — само подлежащее преобразованию (и выводу) значение.

Вторая возможность — функция putchar, выводящая на стандартный вывод заданный символ (код);[4] в данном случае, '\n'управляющий код (или управляющий символ) перевода (разрыва, завершения) строки. Обратите внимание на использование одинарных кавычек при записи символьных констант (в отличие от строковых — для которых используются двойные кавычки.)

Если бы было заранее известно, что значение произведения не превышает, например, 9999, можно было бы обойтись фиксированной разрядностью (" %4ld", i * j — или, что то же, — " %*ld", 4, i * j.) Однако коль скоро в задаче требуется обрабатывать широкий диапазон чисел (наибольшее значение типа long согласно стандарту C11 должно быть не менее порядка 2 × 10⁹), разрядность результата необходимо вычислять исходя из заданного пользователем значения n.

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

Вычисление предельной разрядности[править]

Для получения ровных столбцов в выводе программы, каждое выводимое значение должно состоять из равного количества знаков. Ясно, что из всех возможных произведений i × j, i = 1, …, n, j = 1, …, n, максимальное значение имеет n × n = n2, а значит именно количество знаков в записи этого числа и будет предельным для таблицы умножения n × n.

Далее, мы пользуемся тем фактом, что позиционная (в частности — десятичная) запись числа является его разложением по степеням основания системы счисления. Ясно, что максимальная степень n в разложении положительного целого числа x по степеням основания b равна ⌊logbx⌋, а общее число разрядов (включая единицы — при нулевой степени основания) — на единицу больше n.

Для получения конечной формулы, нам остается лишь воспользоваться следующими простыми свойствами логарифмов:

  • logb (xn) = n logbx;
  • logbx = logax ∕ logab = ln x ∕ ln b.

В итоговом выражении — (int)ceil (2 * log (1 + n) / log (10)) — мы используем функции ceil и log, значением которых являются результат округления «от нуля» (в сторону роста абсолютного значения) и натуральный логарифм аргумента, соответственно. Эти функции являются частью стандартной библиотеки и объявлены в заголовке math.h.[5][6]

Ясно, что данное выражение теряет смысл при n < 0. Кроме того, при n = 0, реализованные нами циклы вычисления—вывода сформируют пустой результат, который также можно считать ошибочным. Чтобы этого избежать, перед вычислением искомого выражения мы требуем (макроподстановкой assert[7]) выполнения условия n >= 1.

Здесь же мы требуем, чтобы значение n не превышало квадратного корня из максимального допустимого значения для используемого нами типа long (макроподстановка LONG_MAXобъявлена в заголовке limits.h стандартной библиотеки.) В противном случае, один или более из результатов умножения может переполнить разрядность данного типа. (Отметим, впрочем, что формирование таблицы умножения теряет практический смысл уже при много меньших значениях n.)

Разбор аргументов командной строки[править]

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

  assert (argc - 1 == 1);
  long n;
  {
    char *tail;
    n = strtol (argv[1], &tail, 0);
    assert (tail > argv[1]);
    assert (*tail == '\0');
  }

Данный фрагмент кода начинается требованием (макроподстановкой assert[7]) наличия единственного аргумента командной строки. Здесь следует отметить, что переменная argc отражает общую длину массива argv, в который входит — нулевым элементом — имя самой программы: argv[0]. Тем самым, условие наличия и единственности аргумента может быть записано как argc == 2 — или же как приведено в коде.

В свою очередь, переменные argc и argv являются аргументами главной функции main, при объявлении ее следующим образом:[8]

int
main (int argc, char *argv[])

Мы объявляем переменную n и, в отдельном вложенном блоке, — указатель tail. Вызываем функцию strtol (объявленную в заголовке stdlib.h) преобразования строкового представления числа в «машинное» — значение типа long;[9] результат сохраняем в переменной n. Первый аргумент функции — строка, подлежащая преобразованию; третий — основание системы счисления, или 0 — для использования правил языка Си для числовых констант (например: 0x12 — 12₁₆; 012 — 12₈; 12 — 12₁₀.)

Функция strtol пропускает любые пробельные символы в начале строки (если они есть) и пытается разобрать следующее за ними число. При этом, указатель на первый же символ (код), не являющийся частью такого числа, помещается по адресу, переданному вторым аргументом (если не 0); в нашем случае — в переменную tail. Кроме того, если за ведущими пробельными символами не следует ничего похожего на число (в соответствии с указанной третьим аргументом формой записи), то по данному адресу помещается значение первого аргумента.

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

  1. tail > argv[1] — некое число было обнаружено в данной строке (и извлечено из нее);
  2. *tail == '\0' — за этим числом сразу же следует признак конца строки (код 0.)

В заключение отметим, что во-первых, можно, конечно, обобщить данную программу на случай произвольного количества аргументов — последовательно обрабатывая их в цикле. (В отсутствие аргументов можно выводить таблицу некоего явно определенного в коде размера; например: 10 × 10.) С другой стороны, возможны и другие обобщения.

Во-вторых, аргументы командной строки используются как правило для передачи данных в дополнение к передаваемым через файловые потоки, и в частности — стандартный ввод. Данную программу можно без значимого ущерба для функциональности или удобства переписать для получения значений n со стандартного ввода — применив цикл, аналогичный рассмотренному в разделе Максимум.

Видимость переменных[править]

В примере выше мы «по мере необходимости», в различных точках программы, определили ряд требуемых нам переменных (n, width, i, j) — пользуясь тем, что стандарт (начиная с версии C11) позволяет определять переменные в любой точке кода, где допустимо утверждение. (В версии C99 и более ранних, определения переменных были допустимы только в начале блока — до первого утверждения.) Возникает вопрос: где именно в коде можно использовать каждую из определенных таким образом переменных?

Областью видимости (англ. scope) переменной (или идентификатора в общем) как правило оказывается часть содержащего переменную блока — от точки определения и до закрытия этого блока. Однако, вложенные блоки могут скрывать переменные вышестоящих блоков, объявляя свои собственные переменные с теми же именами. Так, например, функция foo в следующем примере выведет на стандартный вывод код перевода строки (из переменной a внутреннего блока) и вернет значение 1 (из одноименной переменной внешнего):

static int
foo (void)
{
  int a = 1;
  {
    int a = '\n';
    putchar (a);
  }

  return a;
}

Хорошей практикой представляется определение переменных так, чтобы область их видимости была не большей, чем строго необходимо. (Но не в ущерб ясности кода.) В этом случае, при перемещении (копировании) кода, случайное использование переменной там, где она не имеет смысла, с большей вероятностью будет диагностировано непосредственно реализацией языка.

Вариант «мультисистемный»[править]

Используея нами для преобразования строкового представления числа в «машинное» функция strtol определяет систему счисления по префиксу строкового представления числа. В следующем примере мы частично воссоздаем эту логику для вывода таблицы умножения в шестнадцатеричном, восьмеричном или десятичном представлении в зависимости от способа записи аргумента командной строки.

#include <assert.h>
#include <ctype.h>
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int
main (int argc, char *argv[])
{
  assert (argc - 1 == 1);
  long n;
  int base;
  const char *fmt;
  {
    char *tail;
    n = strtol (argv[1], &tail, 0);
    assert (tail > argv[1]);
    assert (*tail == '\0');

    char *p = strchr (argv[1], '0');
    if (p == 0
	|| (p > argv[1] && isdigit (p[-1]))) {
      base = 10;
      fmt = " %*ld";
    } else if (p[1] == 'x' || p[1] == 'X') {
      base = 16;
      fmt = (p[1] == 'X' ? " %*lX" : " %*lx");
    } else {
      base = 8;
      fmt = " %*lo";
    }
  }

  assert (n >= 1);
  assert (n <= sqrt (LONG_MAX));
  const int width = (int)ceil (2 * log (1 + n) / log (base));

  long i;
  for (i = 1; i <= n; i++) {
    long j;
    for (j = 1; j <= n; j++) {
      printf (fmt, width, i * j);
    }
    putchar ('\n');
  }

  return 0;
}

Пример работы программы (построение таблицы умножения для n = 5 в шестнадцатиричном представлении):

$ ./multable 0X5 
  1  2  3  4  5
  2  4  6  8  A
  3  6  9  C  F
  4  8  C 10 14
  5  A  F 14 19
$ 

По сравнению с исходным вариантом, пример дополнился следующим фрагментом кода:

    char *p = strchr (argv[1], '0');
    if (p == 0
	|| (p > argv[1] && isdigit (p[-1]))) {
      base = 10;
      fmt = " %*ld";
    } else if (p[1] == 'x' || p[1] == 'X') {
      base = 16;
      fmt = (p[1] == 'X' ? " %*lX" : " %*lx");
    } else {
      base = 8;
      fmt = " %*lo";
    }

Кроме того, две из исходных констант (10 при вычислении предельной разрядности и " %*ld" в качестве строки формата функции printf) заменены в данном варианте переменными base и fmt, соответственно.

Во фрагменте выше, мы используем функцию strchr (объявленную в заголовке string.h) поиска первого вхождения символа (кода) в строку[10] — в данном случае, поиска символа 0 в аргументе командной строки.

Функция возвращает нулевой указатель (0 или NULL) если символ не найден.[10] Поскольку это означает, что аргумент командной строки не содержит символа 0 вовсе, очевидно, что он не может содержать его и как часть префикса системы счисления (0x или 0), а значит следует использовать десятичную систему счисления при вычислении предельной разрядности и указатель представления d — «десятичное число»: base = 10; fmt = " %*ld";.

Точно так же обрабатывается случай, когда найденному символу 0 предшествует любая десятичная цифра — p > argv[1] && isdigit (p[-1]). Используемая в этом условии функция isdigit (объявлена в заголовке ctype.h) возвращает истину (отличное от 0 значение) в том и только том случае, когда ее аргумент — десятичная цифра; в противном случае — возвращается 0.[11] Разумеется, обращение к предшествующему символу имеет смысл только в том случае, когда найденный символ 0 не является первым в строке — p > argv[1].

Следующим мы проверяем условие p[1] == 'x' || p[1] == 'X' — наличие после 0 признака шестнадцатиричного представления x или X. В этом случае, base присваивается значение 16, fmt" %*lx" или " %*lX" (в зависимости от регистра символа x в аргументе.)

Наконец, если условия выше (наличие цифры перед 0 или x, X — после) — не выполнены, мы присваиваем base значение 8, fmt" %*lo".

Логика выше не покрывает всех возможных значений аргумента командной строки, однако она вполне корректна — поскольку мы предполагаем успешное завершение функции strtol (используя макроподстановки assert выше — при получении значения n), что уже накладывает нужные нам дополнительные ограничения на запись данного аргумента.

Задания[править]

  1. Измените программу для вывода варианта таблицы в одной из трех альтернативных ориентаций: с обратным (от большего к меньшему) порядком строк; с обратным порядком столбцов; с обратным порядком и строк, и столбцов.
  2. Дополните программу поддержкой неположительных значений n. А именно, для n < 0 следует строить таблицу умножения (n, …, -1) × (n, …, -1); для n = 0 — таблицу из единственного значения 0 × 0 = 0. (Указание: воспользуйтесь функцией fabs.[12])
  3. Дополните программу поддержкой необязательного второго аргумента командной строки, используемого как значение основания системы счисления (2‒16 — не предполагая использования кодовой таблицы ASCII, или же 2‒36 в противном случае; по-умолчанию — использовать десятичную систему счисления.) Указание: используйте известность предельной разрядности результатов для определения символьного массива переменной длины. Вывести результирующую строку на стандартный вывод можно используя функцию printf — с указателем формата %s, или же функцию fputs[13] и предопределенный поток stdout.
  4. Измените программу так, чтобы можно было выводить произвольный прямоугольный «фрагмент» таблицы умножения: (a, …, b) × (c, …, d).

Примечания[править]

  1. 6.8.5.3 The for statement(англ.) WG14 N1570 Committee Draft. ISO/IEC (2011-04-12). Проверено 2012-11-19 г.
  2. 6.8.6.2 The continue statement(англ.) WG14 N1570 Committee Draft. ISO/IEC (2011-04-12). Проверено 2012-11-19 г.
  3. 7.21.6.1 The fprintf function(англ.) WG14 N1570 Committee Draft. ISO/IEC (2011-04-12). Проверено 2012-11-19 г.
  4. 7.21.7.8 The putchar function(англ.) WG14 N1570 Committee Draft. ISO/IEC (2011-04-12). Проверено 2012-11-19 г.
  5. 7.12.9.1 The ceil functions(англ.) WG14 N1570 Committee Draft. ISO/IEC (2011-04-12). Проверено 2012-11-19 г.
  6. 7.12.6.7 The log functions(англ.) WG14 N1570 Committee Draft. ISO/IEC (2011-04-12). Проверено 2012-11-19 г.
  7. а б 7.2.1.1 The assert macro(англ.) WG14 N1570 Committee Draft. ISO/IEC (2011-04-12). Проверено 2012-11-19 г.
  8. 5.1.2.2.1 Program startup(англ.) WG14 N1570 Committee Draft. ISO/IEC (2011-04-12). Проверено 2012-11-19 г.
  9. 7.22.1.4 The strtol, strtoll, strtoul, and strtoull functions(англ.) WG14 N1570 Committee Draft. ISO/IEC (2011-04-12). Проверено 2012-11-19 г.
  10. а б 7.24.5.2 The strchr function(англ.) WG14 N1570 Committee Draft. ISO/IEC (2011-04-12). Проверено 2012-11-19 г.
  11. 7.4.1.5 The isdigit function(англ.) WG14 N1570 Committee Draft. ISO/IEC (2011-04-12). Проверено 2012-11-19 г.
  12. 7.12.7.2 The fabs functions(англ.) WG14 N1570 Committee Draft. ISO/IEC (2011-04-12). Проверено 2012-11-19 г.
  13. 7.21.7.4 The fputs function(англ.) WG14 N1570 Committee Draft. ISO/IEC (2011-04-12). Проверено 2012-11-19 г.