Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / C++ [игнор отключен] [закрыт для гостей] / Интересные сравнения, K&R ex 1.7 / 25 сообщений из 25, страница 1 из 1
21.05.2014, 03:31
    #38647130
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Интересные сравнения, K&R ex 1.7
Здравствуйте.
Вчера думал перед сном об одной задаче. Мне стало интересно, можно ли удалить из строки лишние пробелы без дополнительных массивов, за один проход. Оказалось можно, сегодня я эту задачу решил с утра:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
char buf[] = "     hello   world! next smth_else phone book    sdfkhsd   ";
char* s = buf;
char* e = buf + sizeof(buf)-1;
char* cur = buf;

int main(int argc,char** argv)
{
	int extra_length = 0; //количество символов с конца для удаления, за счёт количества пробелов до них.
	while (s<e + extra_length)
	{
		if (s < e)
		{
			if (*s == ' ')
			{
				char* space_cur = s;
				while (*space_cur == ' ')//ищу последний указатель на текущий поток пробелов 
				{
					space_cur++;
				}
				if (space_cur - s > 1)//если число пробелов больше одного
				{
					extra_length += (space_cur - s - 1);
					s += (space_cur - s-1);
				}
			}
			*cur = *s;
		}
		else if (s>e)
		{
			*cur = ' ';
		}
		cur++;
		s++;
	}
	for (int i = 0; *(buf + i);i++)
	{
		printf("%c", *(buf + i));
	}
	return 0;
}


И буквально через 5 минут после её решения я увидел аналогичное задание у K&R:
K&R ex1-7Напишите программу, которая копирует ввод на вывод, заменяя при этом каждую последовательность из одного или более пробелов на один пробел.

И вспомнил про совет по предыдущей задаче:
maytonРаботать с файлом или с STDIN. Вообще, я-бы решал эту задачу в две фазы.
1) Получить поток (STDIN) текста.
2) Игнорировать переносы. {конецслова}+"-"+"\n"+{начало слова} фильтровать.
3) Фиксировать offset и length максимально длинного слова
4) Повторно вычитать файл (Фаза2) и выдать на выход (STDOUT).

Такой код у меня получился:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
	bool count_space_equal_1 = 0;
	int cur;
	while ((cur=getc(stdin)) != '\n')
	{
		if (cur == ' ')//не нравится эта строчка, тут точно всё нормально ?
		{
			if (count_space_equal_1 == 0)
			{
				count_space_equal_1 = 1;
				putc(cur, stdout);
			}
		}
		else
		{
			count_space_equal_1 = 0;
			putc(cur, stdout);
		}
	}



Собственно, к чему я ? К тому что я был приятно удивлён тем что второй код оказался проще чем первый, может и вам будет интересно :)
Правда, если я нигде не ошибся.
...
Рейтинг: 0 / 0
21.05.2014, 05:16
    #38647135
Anatoly Moskovsky
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Интересные сравнения, K&R ex 1.7
SashaMercuryТакой код у меня получился:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
	bool count_space_equal_1 = 0;
	int cur;
	while ((cur=getc(stdin)) != '\n')
	{
		if (cur == ' ')//не нравится эта строчка, тут точно всё нормально ?
		{
			if (count_space_equal_1 == 0)
			{
				count_space_equal_1 = 1;
				putc(cur, stdout);
			}
		}
		else
		{
			count_space_equal_1 = 0;
			putc(cur, stdout);
		}
	}




Собственно, к чему я ? К тому что я был приятно удивлён тем что второй код оказался проще чем первый, может и вам будет интересно :)
Правда, если я нигде не ошибся.
Удивительно, но этот код парой движений адаптируется для строк :)

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
 char buf[] = "     hello   world! next smth_else phone book    sdfkhsd   ";
char* s = buf;
char* d = buf;       
	bool count_space_equal_1 = 0;
	char cur;
	while ((cur = *s++) != 0)
	{
		if (cur == ' ')//не нравится эта строчка, тут точно всё нормально ?  Да :)
		{
			if (count_space_equal_1 == 0)
			{
				count_space_equal_1 = 1;
				*d++ = cur;
			}
		}
		else
		{
			count_space_equal_1 = 0;
			*d++ = cur;
		}
	}
	*d++ = 0; // конец строки в цикл не попал



ЗЫ. Правда, если я нигде не ошибся.
...
Рейтинг: 0 / 0
21.05.2014, 15:40
    #38647717
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Интересные сравнения, K&R ex 1.7
:D нууу, похоже на правду ;) только не получится так что конец строки будет неккоректный ? Я с телефона,не могу проверить.

Но с потоками красивее код, в любом случае :-) Мне он определенно нравится, особенно фильтрация символов сразу
...
Рейтинг: 0 / 0
21.05.2014, 15:57
    #38647756
Anatoly Moskovsky
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Интересные сравнения, K&R ex 1.7
SashaMercuryD нууу, похоже на правду ;) только не получится так что конец строки будет неккоректный ?
Я бы больше сомневался по поводу первого кода - какой-то он слишком громоздкий (даже проверять лень).
...
Рейтинг: 0 / 0
21.05.2014, 16:10
    #38647782
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Интересные сравнения, K&R ex 1.7
Дело в том, что какая-то часть строки оставалась неизмененной, последняя часть, потому я ввел extra_length.
Я не сомневаюсь по поводу вашего кода :-) я сомневаюсь в том что правильно его понял, завтра проверю себя
...
Рейтинг: 0 / 0
21.05.2014, 16:12
    #38647789
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Интересные сравнения, K&R ex 1.7
Ааа, вы сами установили конец строки ! Не думал что так можно делать, точнее что корректно делать. Теперь буду знать ;) Спасибо !
...
Рейтинг: 0 / 0
21.05.2014, 16:21
    #38647804
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Интересные сравнения, K&R ex 1.7
Как-то у тебя все заумно и сложно. Не надо дырки вычислять. Просто запоминай предыдущий символ и проверяй что текущий символ пробел и предыдущий пробел, если так - пропуск записи текущего символа.
Десять строчек кода.

Спрятал ответ на случай если сам захочешь написать
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
int main(int argc,char** argv)
{
	char prev_char = ' '; // предыдущий символ
	while(*s) {
		if(*s != ' ' || prev_char != ' ') {
			*cur = *s;
			cur++;
		}
		prev_char = *s;
		s++;
	}
	*cur = 0; // ставим конец строки. можешь заменить на заполнение пробелами while(cur < s) ...

	printf("%s\n", buf);
	return 0;
}

...
Рейтинг: 0 / 0
21.05.2014, 17:02
    #38647865
Anatoly Moskovsky
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Интересные сравнения, K&R ex 1.7
SashaMercuryЯ не сомневаюсь по поводу вашего кода :-) я сомневаюсь в том что правильно его понял,
Так это ж ваш код, я алгоритм не менял :)
...
Рейтинг: 0 / 0
22.05.2014, 04:24
    #38648280
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Интересные сравнения, K&R ex 1.7
Dima_TПросто запоминай предыдущий символ и проверяй что текущий символ пробел и предыдущий пробел, если так - пропуск записи текущего символа.

У меня получилось 11 строк, сейчас посмотрю ваш код. Алгоритм мне тоже понравился :-)

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
char buf[] = "      hello   world! next smth_else phone book    sdfkhsd   ";
char* s = buf;
char* cur = buf+1;

int main(int argc,char** argv)
{
	while (*s++)
	{
		(*s == ' ' && *(s - 1) == ' ') ? false : *cur++ = *s;//нет функции dummy()
	}
	*(++cur) = '0';	
}



Anatoly MoskovskyТак это ж ваш код, я алгоритм не менял :)

нет, существенно изменили, вы добавили
Код: plaintext
1.
*d++ = 0; // конец строки в цикл не попал


Меня это смутило, я хотел так сделать, но почему-то считал что это плохо, и потому сразу выкинул эту мысль из головы. Потому я ввёл extra_length , и заполнял её ' '.
...
Рейтинг: 0 / 0
22.05.2014, 04:46
    #38648286
Anatoly Moskovsky
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Интересные сравнения, K&R ex 1.7
SashaMercuryУ меня получилось 11 строк, сейчас посмотрю ваш код. Алгоритм мне тоже понравился :-)

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
char buf[] = "      hello   world! next smth_else phone book    sdfkhsd   ";
char* s = buf;
char* cur = buf+1;

int main(int argc,char** argv)
{
	while (*s++)
	{
		(*s == ' ' && *(s - 1) == ' ') ? false : *cur++ = *s;//нет функции dummy()
	}
	*(++cur) = '0';	
}


Че-то вообще не то.
1) Пропадает первый символ
2) В конце добавляется один мусорный символ: зачем тут преинкремент *(++cur)?
3) Да и сам конец надо символом '\0', а не '0' обозначать
4) Ну и по стилю - оператор ?: для ветвления в данном случае снижает читаемость кода, тут нужен простой if с одной веткой.
...
Рейтинг: 0 / 0
22.05.2014, 05:05
    #38648289
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Интересные сравнения, K&R ex 1.7
Anatoly Moskovsky Че-то вообще не то.
1) Пропадает первый символ
2) В конце добавляется один мусорный символ: зачем тут преинкремент *(++cur)?
3) Да и сам конец надо символом '\0', а не '0' обозначать
4) Ну и по стилю - оператор ?: для ветвления в данном случае снижает читаемость кода, тут нужен простой if с одной веткой.

1) Специально так сделал, в противном случае алгоритм убирает все первые пробелы, как в моём примере строки, а должен остаться один. Потому 1ый символ я не трогаю в любом случае.
2.Согласен
3. Согласен, первый раз так делаю, не знал как правильно.
4. Мне он кажется очень понятным. Даже не просто понятным, а я считаю что именно он тут нужен. Только жаль что нет функции dummy(), о которой писал K&R.

Спасибо за замечания !
...
Рейтинг: 0 / 0
22.05.2014, 06:33
    #38648297
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Интересные сравнения, K&R ex 1.7
SashaMercury
Код: plaintext
1.
		(*s == ' ' && *(s - 1) == ' ') ? false : *cur++ = *s;//нет функции dummy()


Откуда читается *(s - 1) при s = buf ? Поэтому у меня доп.переменная

И выучи законы де Моргана, они часто нужны чтобы не писать подобные корявые if()
Законы де Морганаnot (P and Q) = (not P) or (not Q)
not (P or Q) = (not P) and (not Q)

т.е. понятнее так
Код: plaintext
1.
if(*s != ' ' || *(s - 1) != ' ') *cur++ = *s;



Про остальное Anatoly Moskovsky тебе уже написал.
...
Рейтинг: 0 / 0
22.05.2014, 06:44
    #38648299
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Интересные сравнения, K&R ex 1.7
SashaMercury *(++cur) = '0';

*d++ = 0; // конец строки в цикл не попал

Для понимания:
Символ в одинарных кавычках означает ASCII-код символа, без кавычек - код символа числом, т.е. '0' == 48
символ \ используется для указания непечатных символов, читается в паре со следующим как один:
'\n' == 13 && перевод строки
'\t' == 9 && табуляция
'\0' == 0
...
Рейтинг: 0 / 0
22.05.2014, 07:00
    #38648304
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Интересные сравнения, K&R ex 1.7
Dima T Откуда читается *(s - 1) при s = buf ? Поэтому у меня доп.переменная

Дело в том, что я не трогаю первый символ, и цикл начинаю с buf+1, потому что если в самом начале больше одного пробела, то программа (моя), их все убирала, а нужно чтобы оставила один. законы де Моргана, и математическую логику знаю, и то что вы написали тоже.

Dima TДля понимания:
Символ в одинарных кавычках означает ASCII-код символа, без кавычек - код символа числом, т.е. '0' == 48
символ \ используется для указания непечатных символов, читается в паре со следующим как один:
'\n' == 13 && перевод строки
'\t' == 9 && табуляция
'\0' == 0

Спасибо C:
...
Рейтинг: 0 / 0
22.05.2014, 07:03
    #38648305
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Интересные сравнения, K&R ex 1.7
Стоп, не так.

Вот,
Код: plaintext
1.
2.
3.
4.
while (*s++)
{
smth_do
}



потому для [*(s - 1) при s = buf ?] всё нормально
...
Рейтинг: 0 / 0
22.05.2014, 07:05
    #38648307
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Интересные сравнения, K&R ex 1.7
те у меня нет значения buf для s
...
Рейтинг: 0 / 0
22.05.2014, 07:11
    #38648311
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Интересные сравнения, K&R ex 1.7
SashaMercuryВот,
Код: plaintext
1.
2.
while (*s++)
...


Верно. Это я невнимательно смотрел.
...
Рейтинг: 0 / 0
22.05.2014, 07:26
    #38648314
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Интересные сравнения, K&R ex 1.7
Кстати про законы де Моргана. А точнее про математику. Ранее, я решал диффуры в Maple, не в том смысле что использовал готовые пакеты для решения, а программировал там численные методы для приближённого решения, но я решил что летом (когда появится больше свободного времени),нужно будет начать, и реализовать что-нибудь на Си уже. Хватит мочить ноги :D

ДУ в разы интересней математической логики :)
...
Рейтинг: 0 / 0
22.05.2014, 07:42
    #38648319
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Интересные сравнения, K&R ex 1.7
SashaMercuryДУ в разы интересней математической логики :)
Не путай мягкое с теплым, де Моргана надо знать чтобы сложные условия упрощать, а все остальное - делай раз интересно.
...
Рейтинг: 0 / 0
22.05.2014, 12:07
    #38648715
ДаВот
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Интересные сравнения, K&R ex 1.7
SashaMercury,Ранее, я решал диффуры в Maple. А вот я ровно наоборот. Хорошо зная C++ тратил достаточно много времени на программирование своих математических задач. Потом изучил MathCAD. Очень понравилось. Время программирования сократилось в 3-4 раза по сравнению с C++. Потом выучил Maple. И в конце концов изучил Wolfram Mathematica (да и сейчас местами всегда доучиваю - настолько она огромна) с ее функциональным программированием и почти автоматическим распараллеливанием сложных вычислений. Время программирования сократилось еще 3-4 раза. Объем программ сократился в 4 раза. Правда тексты получаются очень насыщенными. Но достаточно быстро вспоминаются что там за логика, если не перестараться с функциональным программированием. Правда надо немного про ускорение алгоритмов Mathematica почитать. Несколько нетривиальных шагов ускоряют скорость выполнения в 10 раз. А автоматическое распараллеливание правильно написанных алгоритмов - это вообще сказка. Купил проц с 4 ядрами и 8 потоками - стало в 7-8 раз быстрее работать, чем на старом сразу.
...
Рейтинг: 0 / 0
22.05.2014, 13:24
    #38648928
Strangecat
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Интересные сравнения, K&R ex 1.7
В последней версии с++ есть регекспы. На них это элементарно делается. Правда, когда я в последний раз их пробовал, они в gcc не работали.

Вообще есть функция ungetc, которая помещает символ обратно в поток. С её помощью можно код сократить до
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
while ((c=fgetc(stdin)) != EOF){
   putc(c, stdout); 
   if (c == ' '){
       while ((c = fgetc(stdin)) == ' ')
         ;
       ungetc (c, stdin); //следующий fgetc() вернёт вот эту c
   }
}



При написании парсеров откатывать всё назад бывает удобно
...
Рейтинг: 0 / 0
22.05.2014, 13:25
    #38648930
Anatoly Moskovsky
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Интересные сравнения, K&R ex 1.7
ДаВот,

Единственная проблема - 99.99% всех задач автоматизации никакого отношения к математике не имеет :)
...
Рейтинг: 0 / 0
22.05.2014, 13:28
    #38648940
Anatoly Moskovsky
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Интересные сравнения, K&R ex 1.7
SashaMercury1) Специально так сделал, в противном случае алгоритм убирает все первые пробелы, как в моём примере строки, а должен остаться один. Потому 1ый символ я не трогаю в любом случае.
Да, алгоритм при более подробном рассмотрении - таки вроде рабочий.
Но настолько неочевидный, что кажется неверным.
А когда с ходу не понятно что делает алгоритм - это самое худшее что может быть в программе.
...
Рейтинг: 0 / 0
25.05.2014, 09:16
    #38651249
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Интересные сравнения, K&R ex 1.7
Anatoly Moskovsky А когда с ходу не понятно что делает алгоритм - это самое худшее что может быть в программе.

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

В данном конкретном случае, вы возможно правы. Мне сложно оценивать свой код
...
Рейтинг: 0 / 0
25.05.2014, 11:27
    #38651283
Anatoly Moskovsky
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Интересные сравнения, K&R ex 1.7
SashaMercuryДа, это может быть понятно, но маловероятно это решение будет оптимальным.
Не то оптимизируете :)
...
Рейтинг: 0 / 0
Форумы / C++ [игнор отключен] [закрыт для гостей] / Интересные сравнения, K&R ex 1.7 / 25 сообщений из 25, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]