powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / C++ [игнор отключен] [закрыт для гостей] / Интересные сравнения, K&R ex 1.7
25 сообщений из 25, страница 1 из 1
Интересные сравнения, K&R ex 1.7
    #38647130
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Здравствуйте.
Вчера думал перед сном об одной задаче. Мне стало интересно, можно ли удалить из строки лишние пробелы без дополнительных массивов, за один проход. Оказалось можно, сегодня я эту задачу решил с утра:
Код: 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
Интересные сравнения, K&R ex 1.7
    #38647135
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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
Интересные сравнения, K&R ex 1.7
    #38647717
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
:D нууу, похоже на правду ;) только не получится так что конец строки будет неккоректный ? Я с телефона,не могу проверить.

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

Спрятал ответ на случай если сам захочешь написать
Код: 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
Интересные сравнения, K&R ex 1.7
    #38647865
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryЯ не сомневаюсь по поводу вашего кода :-) я сомневаюсь в том что правильно его понял,
Так это ж ваш код, я алгоритм не менял :)
...
Рейтинг: 0 / 0
Интересные сравнения, K&R ex 1.7
    #38648280
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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
Интересные сравнения, K&R ex 1.7
    #38648286
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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
Интересные сравнения, K&R ex 1.7
    #38648289
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Anatoly Moskovsky Че-то вообще не то.
1) Пропадает первый символ
2) В конце добавляется один мусорный символ: зачем тут преинкремент *(++cur)?
3) Да и сам конец надо символом '\0', а не '0' обозначать
4) Ну и по стилю - оператор ?: для ветвления в данном случае снижает читаемость кода, тут нужен простой if с одной веткой.

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

Спасибо за замечания !
...
Рейтинг: 0 / 0
Интересные сравнения, K&R ex 1.7
    #38648297
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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
Интересные сравнения, K&R ex 1.7
    #38648299
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercury *(++cur) = '0';

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

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

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

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

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

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



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


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

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

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

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

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


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