Date Редакция Категория comp Теги C / K&R

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

Новый вариант binsearch():

  /* binsearch2: найти x в v[0] <= v[1] <= ... <= v[n-1] */
  int binsearch2(int x, int v[], int n) {
      int low, high, mid;

      low = 0;
      high = n - 1;
      mid = (low+high) / 2;
      while ( low <= high && x != v[mid] ) {
          if ( x < v[mid] )
                high = mid - 1;
          else
              low = mid + 1;
          mid = (low+high) / 2;
      }
      if ( x == v[mid] )
          return mid;
      else
          return -1;  /* совпадения нет */
  }

Для сравнения времени выполнения нам понадобятся функция clock() модуля time.h. Приведем здесь основную функцию:

  #include <stdio.h>
  #include <time.h>

  int binsearch(int x, int v[], int n);
  int binsearch2(int x, int v[], int n);

  #define MAX_ELEMENT 10
  #define MAX_TEST 2000000000

  int main()
  {
      int i;
      int x = 8;
      int test[MAX_ELEMENT];
      clock_t time;

      printf("test[] = ");
      for ( i = 0; i < MAX_ELEMENT; ++i ) {
          test[i] = 2*i;
          printf("%d ", test[i]);
      }
      printf("\n");

      printf("Position of %d in test[] = %d\n", x, binsearch2(x, test, MAX_ELEMENT));

      for ( i = 0, time = clock(); i < MAX_TEST; ++i )
          binsearch(x, test, MAX_ELEMENT);
      time = clock() - time;
      printf("binsearch() works %lu seconds\n",
             (unsigned long) time / CLOCKS_PER_SEC);

      for ( i = 0, time = clock(); i < MAX_TEST; ++i )
          binsearch2(x, test, MAX_ELEMENT);
      time = clock() - time;
      printf("binsearch2() works %lu seconds\n",
             (unsigned long) time / CLOCKS_PER_SEC);

      return 0;
  }

С удивлением обнаружил, что printf перенесенный на новую строчку после запятой тоже работает.

binsearch0.png

Упражнение 3.2. Напишите функцию escape(s,t), которая при копировании текста из t в s преобразует такие символы, как новая строка и табуляция в "видимые последовательности символов" (вроде \n и \t). Используйте инструкцию switch. Напишите функцию, выполняющую обратное преобразование эскейп-последовательностей в настоящие символы.

"Наследник" упражнения 1.10. Итак, учимся применять switch:

  #include <stdio.h>

  #define MAXLEN 30

  void escape(char s[], char t[]);
  void unescape(char s[], char t[]);

  int main()
  {
      char input[MAXLEN] = "bla\tbla\nbla\n";
      char output[MAXLEN];

      printf("Original   = %s\n", input);
      escape(output, input);
      printf("Escaped    = %s\n", output);
      unescape(input, output);
      printf("Unescaped  = %s\n", input);
      printf("The End\n");

      return 0;
  }

  void escape(char s[], char t[])
  {
      int i, j;

      for (i = 0, j = 0; s[i]; i++, j++)
          switch (t[i]) {
          case '\t':
              s[j++] = '';
              s[j] = 't';
              break;
          case '\n':
              s[j++] = '';
              s[j] = 'n';
              break;
          default:
              s[j] = t[i];
              break;
          }
      s[j] = t[i];  // \0  !
  }

  void unescape(char s[], char t[])
  {
      int i, j;

      for (i = 0, j = 0; s[i]; i++, j++)
          switch (t[i]) {
          case '':
              switch (t[++i]) {
              case 't':
                  s[j] = '\t';
                  break;
              case 'n':
                  s[j] = '\n';
                  break;
              }
              break;
          default:
              s[j] = t[i];
              break;
          }
      s[j] = t[i];
  }

escape0.png

Упражнение 3.3. Напишите функцию expand(s1,s2), заменяющую сокращенную запись наподобие a-z в строке s1 эквивалентной полной записью аbс...хуz в s2. В s1 допускаются буквы (прописные и строчные) и цифры. Следует уметь справляться с такими случаями, как a-b-c, a-z0-9 и -a-b. Считайте знак '-' в начале или в конце s1 обычным символом минус.

Разработаем вначале упрощенный expand() -- для одних только цифр. Будем искать '-' и проверять его соседей, не являются ли они границами диапазона:

#include <stdio.h>
#include <ctype.h>

#define MAXLEN 30

void expand(char s1[], char s2[]);

int main()
{
    char in[MAXLEN] = "-1-67-9-\0";
    char out[MAXLEN];

    printf("s1 = %s\n", in);
    expand(in, out);
    printf("s2 = %s\n", out);

    return 0;
}

void expand(char s1[], char s2[])
{
    int i, j;
    char t;

    for (i = 0, j = 0; s1[i] != '\0'; i++)
    {
        if ( s1[i] == '-' )
        {
            if( isdigit(s1[i-1]) && isdigit(s1[i+1]) && (s1[i-1]<s1[i+1]) )
                for (t = (char)(s1[i-1]+1); t < s1[i+1]; t++)
                    s2[j++] = t;
            else
                s2[j++] = s1[i];
        }
        else
            s2[j++] = s1[i];
    }
    s2[j] = '\0';
}

Проверка, является ли данный символ цифрой, осуществляется функцией isdigit() из ctype.h.

Получаем:

expand0.png

Как видно, для цифр наша функция делает все что нужно. Осталось расширить ее действие на строчные и прописные буквы. Здесь нам помогут islower() и isupper():

void expand(char s1[], char s2[])
{
    int i, j;
    char t;

    for (i = 0, j = 0; s1[i] != '\0'; i++)
    {
        if ( s1[i] == '-' )
        {
            if ( (isdigit(s1[i-1]) && isdigit(s1[i+1]) && (s1[i-1]<s1[i+1])) ||
                 (islower(s1[i-1]) && islower(s1[i+1]) && (s1[i-1]<s1[i+1])) ||
                 (isupper(s1[i-1]) && isupper(s1[i+1]) && (s1[i-1]<s1[i+1])) )
                    for (t = (char)(s1[i-1]+1); t < s1[i+1]; t++)
                        s2[j++] = t;
            else
                s2[j++] = s1[i];
        }
        else
            s2[j++] = s1[i];
    }
    s2[j] = '\0';
}

expand10.png

Если хотите, то можете в качестве упражнения сократить длину логического условия.

Упражнение 3.4. При условии, что для представления чисел используется дополнительный код, наша версия itoa не справляется с самым большим по модулю отрицательным числом, значение которого равняется -(2^n-1), где n -- размер слова. Объясните, чем это вызвано. Модифицируйте программу таким образом, чтобы она давала правильное значение указанного числа независимо от машины, на которой выполняется.

Сначала убедимся, что указанный эффект имеет место. Рассмотрим имеющуюся функцию itoa() (п. 3.6) и дополним ее другой готовой функцией -- reverse() (п. 3.5). Максимальное отрицательное число определяется константой INT_MAX из limits.h. Код выглядит так:

  #include <stdio.h>
  #include <string.h>
  #include <limits.h>

  void itoa(int n, char s[]);
  void reverse(char s[]);

  int main(void) {
      char buffer[20];
      int i = 35;

      printf("Number: %d\n", i);
      itoa(i, buffer); 
      printf("Buffer : %s\n", buffer);

      printf("INT_MIN: %d\n", INT_MIN);
      itoa(INT_MIN, buffer);
      printf("Buffer : %s\n", buffer);

      return 0;
  }

  /* itoa: преобразование n в строку s */
  void itoa(int n, char s[])
  {
      int i, sign;
      if ((sign = n) < 0) /* сохраняем знак */
          n =-n;          /* делаем n положительным */
      i = 0;
      do { /* генерируем цифры в обратном порядке */
      s[i++] = n % 10 + '0';    /* следующая цифра */
      } while ((n /= 10) > 0);  /* исключить ее */
      if (sign < 0)
          s[i++] = '-';
      s[i] = '\0';
      reverse(s);
  }

  void reverse(char s[]) {
      int c, i, j;
      for ( i = 0, j = strlen(s)-1; i < j; i++, j--) {
          c = s[i];
          s[i] = s[j];
          s[j] = c;
      }
  }

В результате получим:

itoa0.png

Вот и проблема! Однако перед тем, как разобраться с ней, нужно разобраться с очередными "трудностями перевода". Текст упражнения во 2-ом англоязычном издании (с. 56) гласит:

"In a two's complement number representation, our version of itoa does not handle the largest negative number, that is, the value of n equal to -(2^(wordsize-1)). Explain why not.

Modify it to print that value correctly, regardless of the machine on which it runs".

Как видим, максимальное отрицательное число в оригинале и переводе отличаются.

Исправленный перевод задания выглядит так:

При условии, что для представления чисел используется дополнительный код, наша версия itoa не справляется с самым большим по модулю отрицательным числом, значение которого равняется -(2^(n-1)), где n -- размер слова. Объясните, чем это вызвано. Модифицируйте программу таким образом, чтобы она давала правильное значение указанного числа независимо от машины, на которой выполняется.

Теперь к объяснениям. Однобитовое целое число без знака изменяется в диапазоне 0...255, а со знаком -- в диапазоне -128...127. Поскольку в нашей функции отрицательное число получается обращением равного ему по модулю положительного числа, то для -128 просто не находится положительного "двойника". Это и вызывает проблему.

Исправляем. Для этого не будем делать число положительным до начала цикла, а в цикле воспользуемся взятием модуля числа -- abs() из stdlib.h:

  /* itoa: преобразование n в строку s */
  void itoa(int n, char s[]) {
      int i, sign;
      sign = n; /* сохраняем знак */

      i = 0;
      do { /* генерируем цифры в обратном порядке */
          s[i++] = abs(n % 10) + '0'; /* следующая цифра */
      } while ( n /= 10 );            /* исключить ее */
      if (sign < 0)
          s[i++] = '-';

      s[i] = '\0';
      reverse(s);
  }

Результат:

itoa10.png

Упражнение 3.5. Напишите функцию itob(n,s,b), которая переводит целое n в строку s, представляющую число по основанию b. В частности, itob(n, s, 16) помещает в s текст числа n в шестнадцатеричном виде.

Обобщаем код из предыдущего упражнения. Проблема представления чисел в системах счисления с b > 10 решается введением массива digits:

  #include <stdio.h>
  #include <string.h>
  #include <stdlib.h>
  #include <limits.h>

  void itob(int n, char s[], int b);
  void reverse(char s[]);

  int main(void) {
      char buffer[100];
      int i = 31;

      printf("Number: %d\n", i);
      itob(i, buffer, 16); 
      printf("Buffer : %s\n", buffer);

      printf("INT_MIN: %d\n", INT_MIN);
      itob(INT_MIN, buffer, 16);
      printf("Buffer : %s\n", buffer);

      return 0;
  }

  /* itob: преобразование n в строку s, представляющую 
   * число по основанию b (2 <= b <= 16)               */
  void itob(int n, char s[], int b) {
      int i, sign;
      char digits[] = "0123456789ABCDEF";

      sign = n; /* сохраняем знак */

      i = 0;
      do { /* генерируем цифры в обратном порядке */
          s[i++] = digits[n % b]; /* следующая цифра */
      } while ( n /= b );         /* исключить ее */
      if (sign < 0)
          s[i++] = '-';

      s[i] = '\0';
      reverse(s);
  }

itob0.png

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

Если окажется, что строковое представление числа превышает минимальную ширину поля minfield, то выдадим предупреждение и выйдем из цикла формирования строки.

  void itoa(int n, char s[], int minfield) {
      int i, sign;
      sign = n;

      i = 0;
      do {
          s[i++] = abs(n % 10) + '0';
          if (i > minfield){
              printf("Warning! String representation is too short!\n");
              break;
          }
      } while ( n /= 10 );
      if (sign < 0)
          s[i++] = '-';
      while (i < minfield)
          s[i++] = ' ';
      s[i] = '\0';
      reverse(s);
  }


Комментарии

comments powered by Disqus