powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / C++ [игнор отключен] [закрыт для гостей] / Решение ряда задач.
100 сообщений из 100, показаны все 4 страниц
Решение ряда задач.
    #38815695
Фотография 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
Решение ряда задач.
    #38815781
Фотография 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
Решение ряда задач.
    #38815871
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ну вы вообще...
Не каждый сможет обратить строку, в смысле, делать это могут не только лишь все...
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38815922
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonНа производительность вляют столько факторов что топика не хватит.
Я-бы предложил подумать над оптимизациями идущими далеко в будущее.
Вообще-то в условии задачи прямо сказано что производительность не важна :)

Это задача на умение генерировать идеи.
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38815950
no56892
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
А еще есть вариант рандомно перемешивать массив символов до тех пор, пока там не появится "строка наоборот".
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38815958
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Будь здесь Базист - он предложил-бы загнать все строки известные науке в его магическую
флористическую базу и вместо реверса просто находить ответную строку через
ультра-быстрый поиск.
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38815963
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
Решение ряда задач.
    #38815994
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakovследовательно простейшим методом будет
что есть "простейший" ?
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38816004
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Дима. Дык твой код вроде как сделает двойной реверс. Не?
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38816007
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Вроде не.
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38816044
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonДима. Дык твой код вроде как сделает двойной реверс. Не?
Обижаешь...
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38816064
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Напомнило. Красивая формула.

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



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

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


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

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



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

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

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




Я где-то читал что есть особая ассемблерная директива машин серии PDP
которая 1:1 соответствует этой строке кода.
Зачем так далеко ходить? Интеловский MOVS умеет и ++ и -- :)
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38816102
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Anatoly MoskovskyИнтеловский MOVS умеет и ++ и -- :)
А умеет он их одновременно? Тогда задачу ТСа можно было бы решить в пять ассемблерных строчек.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38816106
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry SibiryakovAnatoly MoskovskyИнтеловский MOVS умеет и ++ и -- :)
А умеет он их одновременно? Тогда задачу ТСа можно было бы решить в пять ассемблерных строчек.
Неа, не умеет.
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38816141
Фотография 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
Решение ряда задач.
    #38816188
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryА я хочу O(1)
В любом случае для переворота должна быть прочитана вся строка и вся записана, а сколько и какие команды процессора понадобятся - неважно, т.к. сложность алгоритма это не изменит.
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38816223
Фотография 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
Решение ряда задач.
    #38816250
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Интересно где он декларирован? Искал через текстовый поиск по %LISP_HOME% но нашёл только
использование реверса в других *.lisp файлах. Но нету в define/defun/def

Может Илья подскажет.
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38816252
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima TВ любом случае для переворота должна быть прочитана вся строка и вся записана
Mayton выше привел алгоритм без копирования, с флагом.
Так что не в любом случае.
Надо просто шире думать :)
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38816270
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Anatoly MoskovskyНадо просто шире думать :)
Надо шире искать под какой ещё коврик замести потерю времени на реальный реверс.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38816273
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Anatoly MoskovskyMayton выше привел алгоритм без копирования, с флагом.Чтобы выставить флаг, придётся "попарно сверить две половинки строки". И даже тогда может не повезти и копировать всё равно придётся.Надо просто шире думать :)Особенно надо думать о преждевременной оптимизации.
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38816278
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryМы в любом случае перебираем каждый байтЭто пока вы не начали работать с кодировками. Тогда реверс байт будет простым и тривиальным занятием.
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38816283
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Basil A. SidorovЧтобы выставить флаг, придётся "попарно сверить две половинки строки". И даже тогда может не повезти и копировать всё равно придётся.
Джава знает ответ на этот вопрос :)
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38816286
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Anatoly MoskovskyДжава знает ответ на этот вопрос :)Нет, не знает.
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38816290
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я когда-то приводил пример с транспонированием матрицы.
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38816296
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
И что?
Весь APL был сделан на отложенных вычислениях, но работало это только потому, что, как правило, требовалась только часть матрицы.
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38816299
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я Сашику вобщем-то писал.
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38816332
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Basil A. SidorovЧтобы выставить флаг, придётся "попарно сверить две половинки строки". И даже тогда может не повезти и копировать всё равно придётся.
Погодите, причем здесь сравнение половинок?
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38816349
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Вы про разные флаги говорите наверное. Я их 2 штуки предлагал.
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38816381
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Похоже, что - да, про разные.
Но "Swapped=False" - вообще хня.
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38816393
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Иммутабельность, мать ее так... Она заложена во все строковые
объекты .Net/Java. Я просто предложил свой взгляд на задачу реверса в С/С++.

А так - всё чики-пики. Можно и кувыркать символы в мемори.
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38816407
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonИммутабельность, мать ее так... Она заложена во все строковые объекты .Net/Java.Не знаю как в .NET, но в Java неизменяем только java.lang.String. А StringBuilder/StringBuffer - вполне переменные.Я просто предложил свой взгляд на задачу реверса в С/С++.Отложенный реверс - изначально задница: нет места отложенным вычислениям.
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38816477
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Basil A. Sidorov, StringBuffer, StringBuilder не являются строковыми переменными.
Это хелперы которые помогают сформировать всё тот-же самый immutable String на выходе.
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38816521
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonЭто хелперы которые помогают сформировать всё тот-же самый immutable String на выходе.Если String нужен, да, могут быть приведены к строковому типу. А если не нужен:
Код: java
1.
2.
3.
4.
5.
StringBuilder msg = new StringBuilder(25);
msg.append("Раз, ")
   .append("два: ")
   .append(1).append(", ")
   .append(2);

?
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38816528
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я слышу вопрос - "А не заменить-ли все String на StringBuilder" ?
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38816554
petalvik
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Basil A. Sidorov правильно упомянул про кодировки. Я тоже о них сразу подумал.
Поменять однобайтные символы просто. А вот если будут многобайтные кодировки, UTF8 или UTF16 с суррогатными парами, то...
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38816578
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Плавающие кодировки существуют обычно в файлах. В String-объектах это обычно UTF-16.
Индекс вычислется чутка легше чем в утф-8.
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38816593
petalvik
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

да, но у автора голый Си.
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38816595
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
А что для Си не существует поддержки кодировок? В библиотеках хотя-б...
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38816599
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
petalvikПоменять однобайтные символы просто. А вот если будут многобайтные кодировки, UTF8 или UTF16 с суррогатными парами, то...
ничего страшного.
даже если на месте менять.
и без всяких библиотек
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38816601
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Тогда нужно 3 реверса. В скобках замечу что нет однозначных правил по детектированию чё внутри байтэррея.

Код: plaintext
1.
2.
3.
4.
5.
reverseBytes(...);

reverseUtf8Bytes(...);

reversUtf-16bytes(...);
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38816664
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
petalvikПоменять однобайтные символы просто. А вот если будут многобайтные кодировки, UTF8 или UTF16 с суррогатными парами, то...Да хоть UTF32. Составные символы никто не отменял.
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38816837
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Basil A. SidorovSashaMercuryМы в любом случае перебираем каждый байтЭто пока вы не начали работать с кодировками. Тогда реверс байт будет простым и тривиальным занятием.

не говорю что это сложное занятие. Просто хочу решать эту задачу по-другому
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38816841
Фотография 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.
int my_printf(FILE* out, const char* s, size_t p, int(*func)(const char* s, size_t p, int i))
{
	for (int i = 0; i < p; ++i)
		putc(func(s,p,i), out);

	return 0;
}

//function is defined on i in[0,p)
//reverse(x)
int reverse(const char* s, size_t p, int x)
{
	return *(s + p - 1 - x);
}




int main()
{
	char s[] = "Hello, Embarcadero";
	printf("before: %s\n", s);
	size_t p = strlen(s);
	my_printf(stdout, s, p, (*reverse));
	printf("\n");
	return 0;
}
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38816843
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Хм. Пришел к тому, что мне нужно реализовать тип данных который включает в себя строку, и способ её чтения
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38816848
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryХм. Пришел к тому, что мне нужно реализовать тип данных который включает в себя строку, и способ её чтения

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

спецификацию юникода почитай - там много удивительного

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

Unicode equivalence, например
http://en.wikipedia.org/wiki/Unicode_equivalence
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38816854
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Изопропил,

википедия, это не спецификация.
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38816855
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercury,

спецификацию сам откроешь - http://unicode.org

UNICODE NORMALIZATION FORM
http://unicode.org/reports/tr15/
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38817214
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Изопропил,
спасибо за ссылку. Но к сожалению, у меня нет 60-120 минут(а может и больше) на изучение того документа. Это не Си, и не алгоритмы, и не математика. Позже, я обязательно постараюсь прочитать то, к чему вы пытались меня привести. Может быть вы попробуете простыми словами донести до особо одарённых то, что хотели сказать ?
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38817330
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Наверное он хотел сказать что сравнени Unicode символов не равно сравнению байтов.

Если я верно понял суть.
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38817355
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonНаверное он хотел сказать что сравнени Unicode символов не равно сравнению байтов.

Если я верно понял суть.

Ну да, и если крутить символы in-place, то будет сложнее -- символы-то переменной длины
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38817397
RWolf
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
а ещё два символа могут складываться в один знак (буква с диакритикой), так что надо ещё определиться, какой результат мы хотим увидеть после «кручения».
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38817402
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
MasterZivНу да, и если крутить символы in-place, то будет сложнее -- символы-то переменной длины
это самое простое, строку UTF-8 можно читать в любом направлении.

а вот композитные(не путать с суррогатными парами UTF-16) типа

a + ogonek + acute = <U+0061, U+0328, U+0301>

переворачивать несколько сложнее
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38817435
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Возможен ли вообще реверсный итератор по Utf-8 байтовому массиву?

Это как архив читать в обратном направлении.

Особенно в совокупности с копозитными символами.
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38817526
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonВозможен ли вообще реверсный итератор по Utf-8 байтовому массиву?Разумеется возможен.
Отдельная кодовая точка состоит или из байта со сброшенным старшим битом или начинается байтом с двумя установленными старшими битами. Максимальный размер кодовой точки - четыре байта.
Соответственно, при любом направлении прохода по последовательности байт отдельные кодовые точки выделяются с примерно одинаковой (не)эффективностью.
Обработка составных символов от кодировки не зависит.
Всё, что требуется - аккуратно копировать кусочки байт вперёд и назад. Не просто, но реализуемо.
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38817534
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Тоже думаю что возможно.

Кстати думаю что с некоторой структурой данных типа индексации.. можно
не реализовывать чтения Utf8 "взад". А просто "двигать" серединку строки влево.
По аналогии с сортировкой вставками.
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38817537
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Изопропил, не улавливаю связи с тем, о чём я рассуждал.
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38817559
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonВозможен ли вообще реверсный итератор по Utf-8 байтовому массиву?
тривиален -
первый байт многобайтового символа 11xxyyyy
все последующие 10xxyyyy
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38817562
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryИзопропил, не улавливаю связи с тем, о чём я рассуждал.
Хотел строковую библиотеку написать? - не забудь про UTF-8.
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38817567
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Нет. Трудность не в том. Поддержка Utf-8 обычно реализована как фильтр внешних данных.
А все манипуляции со строками в ядре системы должны ходить в Utf-16.

А то чем мы щас занимаемся это онанизм и вариации на тему как-бы впихнуть
"квадратную пробку в круглое отверстие".

Вобщем сон разума порождает чудовищ.
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38817572
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonА все манипуляции со строками в ядре системы должны ходить в Utf-16.Фундаментальное заблуждение.
Корни растут из того факта, что изначально юникод делали по принципу "один символ - один код".
Я бы сказал, что есть два варианта:
1. utf8;
2. Упаковка 21-битных триад в блоки по восемь байт.
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38817623
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

речь об интерпретации композитных символов.

UTF-8 UTF-16 или UTF-32 не имеет ни малейшего значения.
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38817624
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonА все манипуляции со строками в ядре системы должны ходить в Utf-16.
Ну тогда уж UTF-32
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38817652
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Basil A. Sidorov2. Упаковка 21-битных триад в блоки по восемь байт.
Это еще зачем?
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38817653
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ИзопропилmaytonА все манипуляции со строками в ядре системы должны ходить в Utf-16.
Ну тогда уж UTF-32
Не очень понял сарказма. Кому не хватает 64К букв?
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38817661
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonНе очень понял сарказма. Кому не хватает 64К букв?
алгоритму обработки. нечего ветви делать для обработки суррогатных пар.
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38817681
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonНе очень понял сарказма. Кому не хватает 64К букв?Если вы не в курсе, то уже третья версия юникода содержала более ста тысяч (несоставных) символов. Текущая версия - шестая.

P.S. Собственно, 64КБукв не хватило уже тогда, когда Корея, Китай и Япония не договорились о единой схеме кодирования иероглифических символов.
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38817685
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonЭто еще зачем?UTF-16 требует обрабатывать суррогатные пары, UTF-8 и UTF-32 - не требуют.
В UTF-8 - переменное число байт на кодовую точку, в UTF-32 - фиксированное, но бесполезно теряется одиннадцать бит.
Если упаковать 21-битные кодовые точки в битовую структуру, то мы оставляем фиксированное число бит на кодовую точку и достаточно существенно экономим на хранении данных.
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38817714
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Basil A. Sidorovв UTF-32 - фиксированное, но бесполезно теряется одиннадцать бит.
Если упаковать 21-битные кодовые точки в битовую структуру, то мы оставляем фиксированное число бит на кодовую точку и достаточно существенно экономим на хранении данных.
Понятно. Почему-то напомнило Base64.
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38817734
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Долго пытался вспомнить применение реверсу. Что-то такое видел.
В каком ЯП - не скажу точно. Толи делфи толи PowerBuilder Поэтому - псевдокод:


Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
if (f.isFile) then

    if ( startWith(reverse(f.name),".lmx") then

        processFuckenXMLFile(f);

    end;

end;
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38817737
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Или так.

Код: pascal
1.
( startWith(reverse(f.name),"lmx."))
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38817756
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonДолго пытался вспомнить применение реверсусам по себе реверс малоинтересен
разбиение юникодной скроки на кластеры графем - интереснее
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38817757
petalvik
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonДолго пытался вспомнить применение реверсу.
На собеседованиях могут спросить.
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38817762
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

Код: plaintext
1.
startWith(reverse(f.name),".lmx")



За такое сразу уволить без выходного пособия :)
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38817767
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonИли так.
Код: pascal
1.
( startWith(reverse(f.name),"lmx."))

Тогда уж:
Код: pascal
1.
startWith(reverse(f.name), reverse(".xml"))
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38817808
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ИзопропилmaytonДолго пытался вспомнить применение реверсусам по себе реверс малоинтересен
разбиение юникодной скроки на кластеры графем - интереснее
Переход между big/little-endian можно считать реверсом. Вот еще кейс.

По поводу графем - интереснее конечно только углубляться в эту тему
как-то лень.
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38817812
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonПереход между big/little-endian можно считать реверсом.Нельзя.
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38817815
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Сама лаконичность!
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38817819
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Но если очень хочется то можно :)
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38817828
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ну-ну ...
Высказать непродуманную мысль, конечно, можно, но хотелось бы услышать обоснование теоретической возможности сделать преобразование BE/LE на строке в кодировке UTF-8.
Для простоты можно начать с обоснования если не эквивалентности, то хотя бы подобия изменения порядка байт и порядка символов.
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38817830
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Да ладно не парься!
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38817832
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
И не думал. Просто страшно за неокрепшую психику молодёжи
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38820394
petalvik
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Во, наткнулся на реальное применение реверса строк:
Код: sql
1.
SELECT email_address FROM customers WHERE reverse(email_address) LIKE reverse('%@wikipedia.org');


Это чтобы задействовался индекс.
Пруф
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38820400
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
petalvik, ага. Я тоже эту тему вспомнил.
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38820401
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
petalvikЭто чтобы задействовался индекс.
Не, это чтобы не задействовалась первая НФ.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38820456
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Начиная с Oracle11g могли-бы virtual columns создавать. Туда - перевёрнутые имена почтовых доменов.
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38822198
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Здравствуйте.
Привожу третью задачу. (вторая позже)
3 задачаПроверить, является ли целое число счастливым билетом.

Эта задача показалась мне слишком простой. Потому решил следующую задачу:
Что на самом деле нужно решитьНайти количество счастливых билетов, входной параметр -количество символов в билете 2n.
И тут я использовал длинную арифметику. Алгоритм решения привожу ниже:

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.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
132.
133.
134.
135.
136.
137.
138.
139.
140.
141.
142.
143.
144.
145.
146.
147.
148.
149.
150.
151.
152.
153.
154.
155.
156.
157.
158.
159.
160.
161.
162.
163.
164.
165.
166.
167.
168.
169.
170.
171.
172.
173.
174.
175.
176.
177.
178.
179.
180.
181.
182.
183.
184.
185.
186.
187.
188.
189.
190.
191.
192.
193.
194.
195.
196.
197.
198.
199.
200.
201.
202.
203.
204.
205.
206.
207.
208.
209.
210.
211.
212.
213.
214.
215.
216.
217.
218.
219.
220.
221.
222.
223.
224.
225.
226.
227.
228.
229.
230.
231.
232.
233.
234.
235.
236.
237.
238.
239.
240.
241.
242.
243.
244.
245.
246.
247.
248.
249.
250.
251.
252.
253.
254.
255.
256.
257.
258.
259.
260.
261.
262.
263.
264.
265.
266.
267.
268.
269.
270.
271.
272.
273.
274.
275.
276.
277.
278.
279.
280.
281.
282.
283.
284.
285.
286.
287.
288.
// HappyTickets.cpp : Defines the entry point for the console application.
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MIN_POW (1+1)
#define SHIFT '0'


//выделение len Байт
char* allocate_memory(size_t len)
{
	return (char*)malloc(len*sizeof(char));
}

//освобождение памяти
int freeMemory(char* s1, char* s2, int isFreeMemory)
{
	if (isFreeMemory >= 1)
	{
		free(s1);
		s1 = NULL;
	}
	if (isFreeMemory >= 2)
	{
		free(s2);
		s2 = NULL;
	}
	return 0;
}



//СУММА
//s1>=s2
int la_sum_inplace(char* sum, size_t p, char* s1, size_t p1, char* s2, size_t p2)
{
	memset(sum, '0', p); *(sum + p - 1) = '\0';//установка стартового значения
	memcpy(sum + p1 - p2 + 1, s2, p2 - 1);//пишем в конец результирующей строки минимальное число
	int d = 0;
	for (int i = p - 2; i > 0; i--)
	{
		int t0 = *(sum + i) + *(s1 + i - 1) + d - 2 * SHIFT;
		int t1 = t0 % 10;
		*(sum + i) = t1 + '0';
		d = (t0 >= 10) ? 1 : 0;
	}
	if (!d && p != 2)
		memmove(sum, sum + 1, p - 1);
	else
		*(sum + 0) = d + '0';
	return 0;
}

//s1+s2      s1,s2>=0
char* la_sum(char* s1, char* s2, int isFreeMemory)
{
	size_t p[2] = { strlen(s1) + 1, strlen(s2) + 1 };
	int max_i = (p[0] > p[1]) ? 0 : 1; //индекс максимальной строки
	int min_i = 1 - max_i;//индекс минимальной строки
	char* max_s = (max_i == 0) ? s1 : s2;
	char* min_s = (min_i == 0) ? s1 : s2;

	int p_res = p[max_i] + 1;//просим на 1 Байт больше чтобы исключить вероятность повторного аллоцирования
	char* res = allocate_memory(p_res);
	la_sum_inplace(res, p_res, max_s, p[max_i], min_s, p[min_i]);   // calculate in-place   
	freeMemory(s1, s2, isFreeMemory);
	return res;
}




//УМНОЖЕНИЕ 
//s-строка,num-число
//функция оптимизированна под умножение строки на строку за счёт сдвига shift
int la_mul_string_on_num_inplace(char* res, size_t p, char* s, size_t ps, unsigned int num, int sh)
{
	if ((ps == MIN_POW && s[0] == '0') || (num == 0))
	{
		res[0] = '0'; res[1] = '\0';
		return 0;
	}
	memset(res, '0', p);
	int d = 0;
	for (int i = ps - 2; i >= 0; --i)
	{
		int t = (s[i] - SHIFT)*num + d;
		int t1 = t % 10;
		res[i + 1] = t1 + SHIFT;
		d = (t - t1) / 10;
	}
	res[p - 1] = '\0';
	if (!d)
		memmove(res, res + 1, p - 1);
	else
		res[0] = d + SHIFT;
	return 0;
}

//s*num*10^sh
char* la_mul_string_on_num(char* s, unsigned int num, int sh)
{
	size_t ps = strlen(s) + 1;
	size_t p = ps + 1 + sh;//реализую умножение на 10^sh
	char* res = allocate_memory(p);
	la_mul_string_on_num_inplace(res, p, s, ps, num, sh);
	return res;
}


//s1*s2
char* la_mul(char* s1, char* s2, int isFreeMemory)
{
	size_t p1 = strlen(s1) + 1;
	size_t p2 = strlen(s2) + 1;
	size_t p = p1 + p2 - 1;

	char* res = allocate_memory(2); res[0] = '0'; res[1] = '\0';
	for (int i = p2 - 2; i >= 0; --i)
	{
		char* t = la_mul_string_on_num(s1, s2[i] - SHIFT, p2 - 2 - i);
		res = la_sum(res, t, 2);
	}
	freeMemory(s1, s2, isFreeMemory);
	return res;
}


//РАЗНОСТЬ s1-s2 s1>=s2
int la_diff_inplace(char* res, size_t p, const char* s1, size_t p1, const char* s2, size_t p2)
{
	memcpy(res, s1, p);
	for (int i = p - 2; i >= 0; --i)
	{
		if (res[i] - s2[i] >= 0)
		{
			res[i] = res[i] - s2[i] + SHIFT;
		}
		else
		{
			int j;
			for (j = i - 1; res[j] == '0'; --j)
			{
				res[j] = '9';
			}
			res[j] -= 1;
			res[i] = 10 + res[i] - s2[i] + SHIFT;

		}
	}
	int count_0 = 0;
	int z = 0;
	for (; z < p - 1 && res[z] == '0'; ++z);
	if (z)
		memmove(res, res + z, p - z);
	return 0;
}

char* la_diff(char* s1, char* s2, int isFreeMemory)
{
	size_t p1 = strlen(s1) + 1;
	size_t p2 = strlen(s2) + 1;
	size_t p = p1;

	char* ss2 = (char*)malloc(sizeof(char)*p);
	memset(ss2, '0', p);
	memcpy(ss2 + p - p2, s2, p2);//было memcpy(ss2 + p - p2, s2, p2);

	char* res = allocate_memory(p);
	la_diff_inplace(res, p, s1, p, ss2, p);
	free(ss2);
	freeMemory(s1, s2, isFreeMemory);
	return res;
}





struct Number
{
	int num;
	int num2;
	int count;
	int* multipliers;
};

struct Number* initializeNumber(int a)
{
	struct Number* n = (struct Number*)malloc(sizeof(struct Number));
	n->num = a;
	n->num2 = a;
	n->count = 0;
	n->multipliers = NULL;
	return n;
}

int viewNumber(struct Number* a)
{
	printf("num= %i\n", a->num);
	printf("num2= %i\n", a->num2);
	printf("divisors:");
	for (int i = 0; i < a->count; ++i)
	{
		printf("%i ", a->multipliers[i]);
	}
	printf("\n");
	return 0;
}

//assume a->num > 1
int factorization(struct Number* a)
{
	for (int i = 2; i <= a->num2; ++i)
	{
		if (a->num2%i == 0)
		{
			a->count += 1;
			a->multipliers = (int*)realloc(a->multipliers, a->count*sizeof(int));
			a->multipliers[a->count - 1] = i;

			a->num2 /= i;
			factorization(a);
			break;
		}
	}
	return 0;
}
//Сочетания
char* la_combination(unsigned n, unsigned m)
{
	char* res = allocate_memory(2); res[0] = '1'; res[1] = '\0';
	m = (n - m > m) ? m : n - m;
	if (m == 0)
	{
		return res;
	}
	int* up = (int*)malloc(sizeof(int)*m);//числитель
	int* down = (int*)malloc(sizeof(int)*m);//знаменатель

	for (int i = 1; i <= m; ++i)
	{
		*(up + m - i) = n - m + i;
		*(down + m - i) = i;
	}

	int len_down = m;
	for (int i = 0; i < len_down; ++i)//1 проход по знаменателю, длина знаменателя меняется
	{
		int j = 0;
		for (j = 0; j < m; ++j)//проход по числителю
		{
			if (!(up[j] % down[i]))
			{
				up[j] /= down[i];
				break;
			}
		}
		if (j == m && down[i] != 1) //если перебрали все элементы числителя, а фиксированный элемент знаменателя не сократили
		{
			struct Number* n = initializeNumber(down[i]);
			factorization(n); //раскладываю число на множители
			down[i] = 1;
			len_down += n->count;
			down = (int*)realloc(down, sizeof(int)*len_down);
			for (int i = 0; i < n->count; ++i)
			{
				down[len_down - n->count + i] = n->multipliers[i];
			}
			free(n->multipliers);
			free(n);
		}
	}

	char* t = (char*)malloc(10);
	for (int i = 0; i < m; ++i)
	{
		sprintf(t, "%d", up[i]);
		res = la_mul(res, t, 1);
	}
	free(t);
	free(up);
	free(down);
	return res;
}



2 часть Основной алгоритм
Код: 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.
//len=2n
char* countHappyTicket(int n)
{
	char* sn = allocate_memory(5); sprintf(sn, "%i", n);
	int k = 9 * n / 2;
	char* res1 = allocate_memory(2); res1[0] = '0'; res1[1] = '\0';
	for (int i = 0; i < n; i += 2)
	{
		char* t1 = la_combination(2 * n, i);
		char* t2 = la_combination(11 * n - 1 - 10 * i, 2 * n - 1);
		char* t3 = la_mul(t1, t2, 2);
		res1 = la_sum(res1, t3, 2);
	}
	char* res2 = allocate_memory(2); res2[0] = '0'; res2[1] = '\0';
	for (int i = 1; i < n; i += 2)
	{
		char* t1 = la_combination(2 * n, i);
		char* t2 = la_combination(11 * n - 1 - 10 * i, 2 * n - 1);
		char* t3 = la_mul(t1, t2, 2);
		res2 = la_sum(res2, t3, 2);
	}
	char* res = la_diff(res1, res2, 2);
	return res;
}

int main()
{
	char* res = countHappyTicket(3);
	printf("%s", res);
	free(res);
	return 0;
}



ниже, скриншот для длины 1000 (n=500)
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38822203
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
А вот тесты этого кода аналогичной задачи
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38822205
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Как бы вы решали эту задачу ?
Мне кажется, что можно решить проще
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38822229
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ты не поверишь. Эту задачу на SQL.ru тоже решали.
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38822410
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
petalvikmaytonДолго пытался вспомнить применение реверсу.
На собеседованиях могут спросить.

Я единственное что могу вспомнить/придумать -- для построения дерева суффиксов слов для полнотекстового поиска.
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38822416
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
На тему текстового поиска я заготовил замечательную задачку на пятницу.
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38822554
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonТы не поверишь. Эту задачу на SQL.ru тоже решали.

Кажется здесь было решение тривиальной алгоритмической задачи разными подходами и средствами .

И где-то в МССКЛ-Ораклах мерялись длиной execution plan. Не помню точно.
...
Рейтинг: 0 / 0
Решение ряда задач.
    #38822641
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
У нас тут С,С++, а не базы данных. Кстати, очень сомневаюсь что через интеграл возможно найти точное число при длине билета в 1000 символов, например.
...
Рейтинг: 0 / 0
100 сообщений из 100, показаны все 4 страниц
Форумы / C++ [игнор отключен] [закрыт для гостей] / Решение ряда задач.
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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