powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / C++ [игнор отключен] [закрыт для гостей] / Ошибки в функции реверса каждого слова строки
25 сообщений из 151, страница 5 из 7
Ошибки в функции реверса каждого слова строки
    #38569004
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
И еще. Моя функция rev_each_word выше читает память по другому, и делает printf. Как написать функцию kat которая будет принимать имя функции rev_each_word , и записывать в строку все printf от нее ?
...
Рейтинг: 0 / 0
Ошибки в функции реверса каждого слова строки
    #38569015
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryЯ не хочу идти даже до половины строки для реверса
чудес не бывает, нужен алгоритм.
Предложи алгоритм как перевернуть последовательность из 5 элементов меньше чем за 2 действия, при этом за один шаг менять можно только любые два.
12345hello
Вышеописанные алгоритмы (<=> значит обменять значения)
Шаг 1. [1] <=> [5]
Шаг 2. [2] <=> [4]
...
Рейтинг: 0 / 0
Ошибки в функции реверса каждого слова строки
    #38569023
Фотография Анатолий Широков
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryда, вспомнил, я ошибся насчет КиР. Вы правы !
Пересматривал 12 стульев недавно, и запомнилась фраза про радикально черный-цвет усов :D
Есть ли другой метод ? Я не хочу идти даже до половины строки для реверса, я хочу сделать это в 10 раз быстрее и не в лоб. Как ? Это возможно ?

конечно возможно с помощью оптического процессора - один квант и отражение от зеркала дает реверс.
...
Рейтинг: 0 / 0
Ошибки в функции реверса каждого слова строки
    #38569033
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Сейчас, как я понял, для реверса нужно n/2 итераций по две замены в каждой, кстати, может быть быстрее 1 итерация с n заменами сразу, но не суть. Возможно для n= 10^20 f e существует другой алгоритм
...
Рейтинг: 0 / 0
Ошибки в функции реверса каждого слова строки
    #38569038
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
У меня уже закрываются глаза..завтра буду читать про квант.
Спасибо всем C: Спокойных выходных :)
...
Рейтинг: 0 / 0
Ошибки в функции реверса каждого слова строки
    #38569043
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryИ еще. Моя функция rev_each_word выше читает память по другому, и делает printf. Как написать функцию kat которая будет принимать имя функции rev_each_word , и записывать в строку все printf от нее ?
Можно, но это очень нездоровый путь, т.к. писать выведенное надо будет в другое место (другой массив), проще сразу писать в другой массив.
...
Рейтинг: 0 / 0
Ошибки в функции реверса каждого слова строки
    #38569051
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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.
#include <stdio.h>

char* reverse(char *b) {
    char* h = b;

	char* e = b;
	while(*e != 0 && *e != ' ') e++;
	if(*e != 0) reverse(e + 1);

    for(; b < --e; ++b) {
        char t = *b;
        *b = *e;
        *e = t;
    }
    return h;
}

int _tmain(int argc, _TCHAR* argv[])
{
	char temp[]="Hello world" ;
	printf("%s\n", temp);
	reverse(temp);
	printf("%s\n", temp);

	return 0;
}


Красиво, но неэффективно с точки зрения производительности.
...
Рейтинг: 0 / 0
Ошибки в функции реверса каждого слова строки
    #38569133
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryСейчас, как я понял, для реверса нужно n/2 итераций по две замены в каждой, кстати, может быть быстрее 1 итерация с n заменами сразу, но не суть. Возможно для n= 10^20 f e существует другой алгоритм


Как бы меньше чем за O(N) не получится.
N или N/2.

Это конечно хорошо бы формально доказать, но так навскидку вполне очевидно.
...
Рейтинг: 0 / 0
Ошибки в функции реверса каждого слова строки
    #38569157
Фотография Анатолий Широков
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
MasterZiv,

что здесь формально доказывать, что нужно (int)(N/2) обменов? Как ни крути, O(N)
...
Рейтинг: 0 / 0
Ошибки в функции реверса каждого слова строки
    #38569192
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Тут не обойтись без гипотезы Пуанкаре
...
Рейтинг: 0 / 0
Ошибки в функции реверса каждого слова строки
    #38569193
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Анатолий ШироковMasterZiv,

что здесь формально доказывать, что нужно (int)(N/2) обменов? Как ни крути, O(N)

Да, что нужно N/2 обменов.
...
Рейтинг: 0 / 0
Ошибки в функции реверса каждого слова строки
    #38569194
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
На ограниченном множестве {X} можно построить дешифратор
и минимизировать его. Какой будет O(n) - Х.З.
...
Рейтинг: 0 / 0
Ошибки в функции реверса каждого слова строки
    #38569198
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonНа ограниченном множестве {X} можно построить дешифратор
и минимизировать его. Какой будет O(n) - Х.З.
Кстати, а если n операций запустить параллельно в n потоках, то сложность такого алгорима будет уже О(1) или все-таки еще О(n)? Что там математика про распараллеливание говорит?
...
Рейтинг: 0 / 0
Ошибки в функции реверса каждого слова строки
    #38569204
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Теория алгоритмов эту тему не рассматривает. Но есть IMHO
смежные области, которые смотрят в Сети-Петри, Марковские процессы и прочее.

P.S. И еще IMHO это экстенсивное развиние It. Поэтому неправославно.
...
Рейтинг: 0 / 0
Ошибки в функции реверса каждого слова строки
    #38569401
Фотография Анатолий Широков
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Anatoly Moskovsky,

сам запуск N/2 потоков имеет сложность O(N)
...
Рейтинг: 0 / 0
Ошибки в функции реверса каждого слова строки
    #38569415
Mozok
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
MasterZivКак бы меньше чем за O(N) не получится.
N или N/2.

Это конечно хорошо бы формально доказать, но так навскидку вполне очевидно.
Реверс за О(1):
Код: plaintext
1.
2.
LDMIA r9!, {r0-r7}
STMDB r9!, {r0-r7}


Правда заработает только на армах .
...
Рейтинг: 0 / 0
Ошибки в функции реверса каждого слова строки
    #38570022
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Здравствуйте.

Анатолий Широков
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
// реверс последовательности символов, заданной полуоткрытым диапазоном [b, e)
char* reverse(char *b, char *e) {
    char* h = b;
    for(; b < --e; ++b) {
        char t = *b;
        *b = *e;
        *e = t;
    }
    return h;
}



Я вновь вернулся к вашему коду. Переписал его по своему.
Алгоритм хороший.
а)Но мне не понравилось что интервал полузакрытый, я понимаю что вы вероятнее всего сделали это для Си-строк, чтобы не учитывать конец строки автоматом. Но всё же, мне кажется лучше функция реверса для закрытого участка байт.
б)У K&R тоже реализация через for, но мне кажется while будет красивее, ибо в коде

Код: plaintext
1.
for(; b < --e; ++b) 



легче допустить ошибку.

Хотя, опять таки это вероятно мне легче допустить ошибку, а для остальных в сообществе это очевидно. Потому в корректности данного комментария я не уверен. И потому это просто моё мнение C:

в) обратил внимание на участок кода в for
Код: plaintext
1.
char t = *b;


те фактически я постоянно объявляю новую переменную t, мне кажется что объявление лучше сделать выше. До цикла.

В связи с моими наблюдениями я решил переписать код(точнее я написал его до вас, а потом посмотрел как сделали вы, но ничего не работало из константного массива символом, и мне пришлось более детально разобрать и ваш и мой код)

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
//реверс закрытого промежутка байт [start,end]
void reverse(char* start, char* end) //адрес первого и последнего байта
{
	char temp = 'a'; /*1*/
	while (start<=end)
	{
		char temp = *start;
		*start = *end;
		*end = temp;
		++start; 
		--end;
	}
} 



1. Как лучше инициализировать объект char ? (я знаю что все элементы надо/желательно инициализировать)

Сейчас попробую кое-что сделать, позже выложу.

Заключение: Рассуждения выше, ни в коем случае не есть критика вашего кода. Ибо я понимаю, что вы написали чтобы помочь, и не стремясь к идеалам по качеству кода. Но тем не менее мне интересно имеют ли мои комментарии право на жизнь, либо они идут от того что я пока слишком слабо понимаю Си.
...
Рейтинг: 0 / 0
Ошибки в функции реверса каждого слова строки
    #38570030
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
PS Ошибка выше. Забыл убрать char temp в цикле

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
//реверс закрытого промежутка байт [start,end]
void reverse(char* start, char* end) //адрес первого и последнего байта
{
	char temp = 'a'; /*1*/
	while (start<=end)
	{
		temp = *start;
		*start = *end;
		*end = temp;
		++start; 
		--end;
	}
} 
...
Рейтинг: 0 / 0
Ошибки в функции реверса каждого слова строки
    #38570032
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
next PS.
Лишняя итерация while(start<=end)

Надо так.
//реверс закрытого промежутка байт [start,end]
void reverse(char* start, char* end) //адрес первого и последнего байта
{
char temp = 'a'; /*1.1-1.2*/
while (start<end)
{
char temp = *start;
*start = *end;
*end = temp;
++start;
--end;
}
}
...
Рейтинг: 0 / 0
Ошибки в функции реверса каждого слова строки
    #38570035
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryPS Ошибка выше. Забыл убрать char temp в цикле
Правильнее оставить его в цикле. Как выше писали не надо давать переменной область видимости больше чем это требует алгоритм.

И инициализация (= 'a') не имеет никакой полезной нагрузки, просто будут выполнены бесполезные действия.

Твой код работать будет, но лучше так написать
Код: plaintext
1.
2.
3.
4.
5.
6.
void reverse(char* start, char* end) //адрес первого и последнего байта
{
	while (start<end)
	{
		char temp = *start;
...
...
Рейтинг: 0 / 0
Ошибки в функции реверса каждого слова строки
    #38570077
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima_TПравильнее оставить его в цикле. Как выше писали не надо давать переменной область видимости больше чем это требует алгоритм.


Но я ведь постоянно обновляю новую переменную, постоянно прошу компилятор выделить для неё память ?Или нет ? Я понимаю что лучше объявлять переменную в месте её первого использования, но мне казалось что когда диалог доходит до циклов, это правило немного меняется, и переменную лучше объявить перед началом цикла.

Dima_TИ инициализация (= 'a') не имеет никакой полезной нагрузки, просто будут выполнены бесполезные действия.


Понимаю Вас. Но может в дальнейшем при поиске ошибок я бы увидел что в какой переменной char всегда хранится 'a', и я подумал бы тогда, я ведь не инициализировал её, в том смысле я бы знал что при объявлении переменных типа char по дефолту будет 'a'(всегд буду инициализировать переменные при объявлении определённым числом/кодом). Может быть это излишки.


Дописал функцию принимающую указатель на начало строки и делающую инверсию каждого слова в строке.
Код: 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.
//реверс закрытого промежутка байт [start,end]
void reverse(char* start, char* end) //адрес первого и последнего байта
{
	while (start<end)
	{
		char temp = *start;
		*start = *end;
		*end = temp;
		++start; 
		--end;
	}
} 

void reverse_each_word(char* start)//указатель на начало строки
{
	char* range_s = start;
	char* range_e = start;

	while (*start)//иду по всей строке
	{	
		if (*start == ' ')
		{
			reverse(range_s, range_e-1);
			range_s = start + 1;
		}
		else
		{
			++range_e;
		}
		++start; //иду к следующему элементу строки
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	char test[] = "Hello world";
	reverse_each_word(test);
	printf("%s", test);
}



Теперь нужно внимательно изучить код Анатолия Широкова и ваш
...
Рейтинг: 0 / 0
Ошибки в функции реверса каждого слова строки
    #38570100
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryDima_TПравильнее оставить его в цикле. Как выше писали не надо давать переменной область видимости больше чем это требует алгоритм.


Но я ведь постоянно обновляю новую переменную, постоянно прошу компилятор выделить для неё память ?Или нет ?
Нет. Компилятор сам "догадывается" что не надо выделять память каждый раз. Если посмотреть во что компилируются оба варианта то видно что там одно и тоже (при отладке правая кнопка "go to disassembly")

Выделение памяти под локальные переменные происходит в момент компиляции, в код вписывается что-то типа "использовать 20ю ячейку стэка под переменную temp", а сам код делает примерно следующее
Код: plaintext
1.
2.
3.
char temp = *start; // записать *start в 20ю ячейку стека
*start = *end;
*end = temp; // записать в *end из 20й ячейки стека


т.е. в процессе выполнения никаких операций по выделению/освобождению памяти не происходит. Точнее при старте программы выделяется память под стек и далее используется под все локальные переменные.
Компилятор просто собирает код так чтобы в 20ю ячейку ничего не было записано пока используется переменная temp. Отсюда также вытекает что объявив temp за циклом ты запрещаешь использовать 20ю ячейку на протяжении выполнения всей функции.

В общем пока не заморачивайся. Будешь следить за выделением/освобождением памяти когда явно будешь использовать выделение памяти calloc(), malloc(), new и т.д.

SashaMercury... при поиске ошибок я бы увидел что в какой переменной char всегда хранится 'a', и я подумал бы тогда, я ведь не инициализировал её...
Инициализируй лучше нулем.
...
Рейтинг: 0 / 0
Ошибки в функции реверса каждого слова строки
    #38570105
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
В твоей функции reverse_each_word() лишняя переменная range_e
...
Рейтинг: 0 / 0
Ошибки в функции реверса каждого слова строки
    #38570115
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima_TВ твоей функции reverse_each_word() лишняя переменная range_e


Спасибо, и ещё одна ошибка была. Исправил

Код: 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.
//реверс закрытого промежутка байт [start,end]
void reverse(char* start, char* end) //адрес первого и последнего байта
{
	while (start<end)
	{
		char temp = *start;
		*start = *end;
		*end = temp;
		++start; 
		--end;
	}
} 
//реверс строки с указанного байта
void reverse_each_word(char* current)//указатель на стартовый байт для реверса
{
	char* range_s = current;
	while (*current)//иду по всей строке
	{	
		if (*current == ' ' || *(current+1)=='\0')
		{
			reverse(range_s, current-1);
			range_s = current + 1;
		}
		++current; //иду к следующему элементу строки
	}
}
...
Рейтинг: 0 / 0
Ошибки в функции реверса каждого слова строки
    #38570119
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryСпасибо, и ещё одна ошибка была. Исправил
Уверен что все ошибки исправил?
Смотри внимательно что в результате получается.
...
Рейтинг: 0 / 0
25 сообщений из 151, страница 5 из 7
Форумы / C++ [игнор отключен] [закрыт для гостей] / Ошибки в функции реверса каждого слова строки
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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