Упражнение 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 перенесенный на новую строчку после запятой тоже работает.
Упражнение 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];
}
Упражнение 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.
Получаем:
Как видно, для цифр наша функция делает все что нужно. Осталось расширить ее действие на строчные и прописные буквы. Здесь нам помогут 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';
}
Если хотите, то можете в качестве упражнения сократить длину логического условия.
Упражнение 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;
}
}
В результате получим:
Вот и проблема! Однако перед тем, как разобраться с ней, нужно разобраться с очередными "трудностями перевода". Текст упражнения во 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);
}
Результат:
Упражнение 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);
}
Упражнение 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