Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / C++ [игнор отключен] [закрыт для гостей] / Решение ряда задач. / 25 сообщений из 100, страница 1 из 4
  1  все
25.11.2014, 04:14
    #38815695
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение ряда задач.
Здравствуйте.
Случайно наткнулся в журнале на задачи от одной компании, (название которой я писать не буду ибо не хочу что-то пиарить, пусть и на фоне), и решил размяться Да, решения этих задач можно отправить в компанию, не знаю зачем, какие-то призы вероятно, но срок уже истек, это сентябрьский номер, так что вы не подумайте что я преследую личную выгоду от того, что спрашиваю у вас что-либо по этому поводу.

Вообще дано 6 задач. Сейчас решил первую.
задача 1Дана строка "Hello, Embarcadero". Не обращая внимание на производительность, написать как можно больше вариантов , как поменять символы местами в обратном порядке. Варианты могут отличаться лишь синтаксисом. Можно использовать библиотечные функции работы со строками, но должны быть варианты и без них.\

Вот как я её решил

1 вариант
Код: 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.
#include <stdio.h>
#include <string.h>

int swap_2symb(char* a, char* b)
{
	char t = *a;
	*a = *b;
	*b = t;
	return 0;
}

int reverse_in_place(char* s, size_t p)
{
	for (size_t i=0; i < p / 2; ++i)
		swap_2symb(s + i, s + p - 1 - i);

	return 0;
}


int main()
{
	char s[] = "Hello, Embarcadero";
	printf("before: %s\n", s);
	reverse_in_place(s, strlen(s));
	printf("after: %s\n", s);
	return 0;
}



2 вариант, аналогично, но реализовал функцию strlen

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
#include <stdio.h>


size_t strlen(const char* s)
{
	size_t p = 0;
	while (*s++)
		++p;

	return p;
}



3 вариант
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
int reverse_in_place(char* res, const char* s, size_t p)
{
	for (size_t i = 0; i < p; ++i)
		*(res + p - 1 - i) = *(s + i);

	*(res + p) = '\0';
	return 0;
}

char* reverse(const char* s)
{
	size_t p = strlen(s);
	char* res = (char*)malloc(sizeof(char)*(p+1));
	reverse_in_place(res, s, p);
	return res;
}



4 вариант, тут добавил указатели
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
int reverse_in_place(char* res, const char* s, size_t p)
{
	for (int i = p - 1; i >= 0; --i)
		*res++ = *(s + i);

	*res = '\0';
	return 0;
}



можно еще написать функцию принимающую адреса начала и конца строки, и делать её реверс, можно сделать реверс каждого слова, можно своп делать по-другому. Других вариантов в голову не приходит. Но ведь должен быть в задаче подвох ? Она кажется слишком простой. Как бы вы её решали ?
Кстати, в условии задачи меня смутила фраза про производительность. Что авторы хотели этим сказать ?

PS
остальные 5 задач выложу позже.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.11.2014, 09:24
    #38815781
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение ряда задач.
На производительность вляют столько факторов что топика не хватит.
Я-бы предложил подумать над оптимизациями идущими далеко в будущее.

1) Всегда-ли нужно свапировать? Может быть строка уже зеркально-симметрична
Я исхожу из предположения что запись в память - дорого стоит с точки
зрения кешей и синхронизаций. И лучше ее (запись) вообще не делать
до самого последнего времени. Максимальная иммутабельность.

2) Предлагаю вообще не свапировать длинные строки (более 255 символов к примеру).
Но хранить для них булево свойство.

Код: plaintext
1.
bool isSwapped=false;



Если кто-то если захочет получить распечатать строку на экране или получить
перевёрнутый порядок - то мы ему отдадим геттер или итератор который
вернёт символы в том порядке который соответствует isSwapped.
Это отчасти соответствует принципам lazy-evaluation.

Методы конкатенаций и поиска подстрок также должны учитывать свойство
isSwapped.

Предлагаю также считать верным тезисы

Код: plaintext
1.
reverse(reverse(A)) == A



Если строка - является палиндромом или из 1 символа то

Код: plaintext
1.
reverse(A)==A



Признак палиндромности isPalindrom=true можно также хранить в объекте строки.

3) Возможно существуют и низкоуровневые (ассемблерные) оптимизации этой задачи
основанные на знаниях команд современных CPU и возможностей железа в плане
управления кешами.

Вобщем у меня - всё.

Задача в чистом виде - тоесть именно свапирование букв в memory мне кажется
ненужной. Тем более что в форуме эта задача уже звучала.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.11.2014, 11:05
    #38815871
MasterZiv
MasterZiv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение ряда задач.
Ну вы вообще...
Не каждый сможет обратить строку, в смысле, делать это могут не только лишь все...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.11.2014, 12:07
    #38815922
Anatoly Moskovsky
Anatoly Moskovsky
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение ряда задач.
maytonНа производительность вляют столько факторов что топика не хватит.
Я-бы предложил подумать над оптимизациями идущими далеко в будущее.
Вообще-то в условии задачи прямо сказано что производительность не важна :)

Это задача на умение генерировать идеи.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.11.2014, 12:28
    #38815950
no56892
no56892
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение ряда задач.
А еще есть вариант рандомно перемешивать массив символов до тех пор, пока там не появится "строка наоборот".
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.11.2014, 12:35
    #38815958
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение ряда задач.
Будь здесь Базист - он предложил-бы загнать все строки известные науке в его магическую
флористическую базу и вместо реверса просто находить ответную строку через
ультра-быстрый поиск.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.11.2014, 12:39
    #38815963
Dimitry Sibiryakov
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение ряда задач.
SashaMercuryНо ведь должен быть в задаче подвох ?
Подвох номер 1: про системную функцию ReverseString() они не зря упомянули.
Подвох номер 2: про "in-place" нигде не сказано, следовательно простейшим методом будет
копирование в новый буфер.

Ну и странно, что тебе не пришёл в голову простейший вариант:
Код: sql
1.
2.
3.
4.
5.
6.
7.
char* end = strchr(str,0);
while (str < end)
{
   char c = *str;
   *str++ = *--end;
   *end = c;
}


Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.11.2014, 12:58
    #38815994
Изопропил
Изопропил
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение ряда задач.
Dimitry Sibiryakovследовательно простейшим методом будет
что есть "простейший" ?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.11.2014, 13:04
    #38816004
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение ряда задач.
Дима. Дык твой код вроде как сделает двойной реверс. Не?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.11.2014, 13:08
    #38816007
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение ряда задач.
Вроде не.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.11.2014, 13:31
    #38816044
Dimitry Sibiryakov
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение ряда задач.
maytonДима. Дык твой код вроде как сделает двойной реверс. Не?
Обижаешь...
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.11.2014, 13:45
    #38816064
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение ряда задач.
Напомнило. Красивая формула.

Код: plaintext
1.
*str1++ = *str2++;



Я где-то читал что есть особая ассемблерная директива машин серии PDP
которая 1:1 соответствует этой строке кода.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.11.2014, 13:56
    #38816082
MasterZiv
MasterZiv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение ряда задач.
maytonБудь здесь Базист - он предложил-бы загнать все строки известные науке в его магическую
флористическую базу и вместо реверса просто находить ответную строку через
ультра-быстрый поиск.

Лучше сделать мемоизацию.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.11.2014, 13:59
    #38816087
Dimitry Sibiryakov
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение ряда задач.
maytonЯ где-то читал что есть особая ассемблерная директива машин серии PDP которая
1:1 соответствует этой строке кода.
Есть. ЕМНИП:
Код: sql
1.
	MOVB	(R1)+, (R0)+


В машинном коде - 113130.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.11.2014, 13:59
    #38816088
MasterZiv
MasterZiv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение ряда задач.
maytonНапомнило. Красивая формула.

Код: plaintext
1.
*str1++ = *str2++;



Я где-то читал что есть особая ассемблерная директива машин серии PDP
которая 1:1 соответствует этой строке кода.

Так и в интеле есть MOVS -- копирование строки заранее определённой длины.
Она делает это вместе с охватывающим циклом.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.11.2014, 13:59
    #38816089
Anatoly Moskovsky
Anatoly Moskovsky
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение ряда задач.
maytonНапомнило. Красивая формула.

Код: plaintext
1.
*str1++ = *str2++;




Я где-то читал что есть особая ассемблерная директива машин серии PDP
которая 1:1 соответствует этой строке кода.
Зачем так далеко ходить? Интеловский MOVS умеет и ++ и -- :)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.11.2014, 14:06
    #38816102
Dimitry Sibiryakov
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение ряда задач.
Anatoly MoskovskyИнтеловский MOVS умеет и ++ и -- :)
А умеет он их одновременно? Тогда задачу ТСа можно было бы решить в пять ассемблерных строчек.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.11.2014, 14:07
    #38816106
Anatoly Moskovsky
Anatoly Moskovsky
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение ряда задач.
Dimitry SibiryakovAnatoly MoskovskyИнтеловский MOVS умеет и ++ и -- :)
А умеет он их одновременно? Тогда задачу ТСа можно было бы решить в пять ассемблерных строчек.
Неа, не умеет.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.11.2014, 14:30
    #38816141
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение ряда задач.
Да, тема действительно звучала. И я не вижу проблем в том, чтобы решить эту задачу. Меня и раньше, и сейчас, постоянно, смущает ограниченность. Мы в любом случае перебираем каждый байт. Увидел код копирования Марка строки r to l, и ваши комментарии о том, что существует ассемблерная команда позволяющая это сделать проще. Проще ли ? А эта команда всё-равно будет идти побайтово ? Вероятно так. В любом случае, у нас ограничения, и мы упираемся в эти O(n). А я хочу O(1). Было бы хорошо, если бы могли читать память в обратном порядке, но это позволило бы нам решить лишь часть задач. Например, у нас есть функция f(x)=x+3, и оператор Pz(x)=z(x)^2, т.о. Pf(x)=(x+3)^2, мы в одно действие получаем новое отображение, и нам не нужно менять значение каждой точки, было 3, теперь будет 9, было 4, теперь 16. Что-то аналогичное мне и хотелось увидеть в качестве алгоритма решения данной задачи
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.11.2014, 15:05
    #38816188
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение ряда задач.
SashaMercuryА я хочу O(1)
В любом случае для переворота должна быть прочитана вся строка и вся записана, а сколько и какие команды процессора понадобятся - неважно, т.к. сложность алгоритма это не изменит.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.11.2014, 15:34
    #38816223
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение ряда задач.
Хм... интересненько.

CNU Clisp 2.49
Код: python
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
[1]> (reverse '(1 2 3))
(3 2 1)
[2]> (reverse "Hello")
"olleH"
[3]> (reverse '('H' 'e'))

*** - READ from
       #<INPUT CONCATENATED-STREAM #<INPUT STRING-INPUT-STREAM>
         #<IO TERMINAL-STREAM>>
      : an object cannot start with #\)
The following restarts are available:
ABORT          :R1      Abort main loop
Break 1 [4]> abort
[5]> (reverse '("H" "e"))
("e" "H")
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.11.2014, 15:46
    #38816250
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение ряда задач.
Интересно где он декларирован? Искал через текстовый поиск по %LISP_HOME% но нашёл только
использование реверса в других *.lisp файлах. Но нету в define/defun/def

Может Илья подскажет.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.11.2014, 15:48
    #38816252
Anatoly Moskovsky
Anatoly Moskovsky
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение ряда задач.
Dima TВ любом случае для переворота должна быть прочитана вся строка и вся записана
Mayton выше привел алгоритм без копирования, с флагом.
Так что не в любом случае.
Надо просто шире думать :)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.11.2014, 15:57
    #38816270
Dimitry Sibiryakov
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение ряда задач.
Anatoly MoskovskyНадо просто шире думать :)
Надо шире искать под какой ещё коврик замести потерю времени на реальный реверс.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.11.2014, 16:00
    #38816273
Basil A. Sidorov
Basil A. Sidorov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение ряда задач.
Anatoly MoskovskyMayton выше привел алгоритм без копирования, с флагом.Чтобы выставить флаг, придётся "попарно сверить две половинки строки". И даже тогда может не повезти и копировать всё равно придётся.Надо просто шире думать :)Особенно надо думать о преждевременной оптимизации.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
  1  все
Форумы / C++ [игнор отключен] [закрыт для гостей] / Решение ряда задач. / 25 сообщений из 100, страница 1 из 4
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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