Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / C++ [игнор отключен] [закрыт для гостей] / Решение одной задачи. Вопросы по программному коду и способам реализации. / 25 сообщений из 41, страница 1 из 2
  1  все
26.08.2014, 06:53
    #38728617
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение одной задачи. Вопросы по программному коду и способам реализации.
Здравствуйте.
Уже второй день решаю одну задачу, я думаю она покажется вам интересной. Но пока, не буду её выкладывать сюда, потому что боюсь что кто-нибудь решит её к завтрашнему утру, а я хочу решить её сам. Уже понял как её можно решить, но думаю, что с большой долей вероятности, есть способ более оптимальный, и возможно/вполне веротяно более красивый.

Резюмируя: до пятницы обещаю показать эту задачу, и всё то, что сделал (возможно кому-то будет интересно, но я выложу решение в спойлере, чтобы те кто захочет решить её самостоятельно, могли сами подумать о том, как её решать). Тема называется так не из-за того, что я спрошу ниже, а из-за того, что спрошу у вас позже.


1. 10% необходимых мне для решения этой задачи, это понимание того как правильно собрать все возможные варианты массива, исходя из значения стартового вектора. У нас есть два положительных целых числа одинакового порядка, и взаимно-однозначным отношением между множествами значений разрядов каждого числа.(если представить каждое число как массив из его разрядов, и отсортировать каждый массив в одинаковом порядке, то мы получим два идентичных массива. )

Например: 1233 3321 3123 2133.. и. т.д. Взять два любых числа отсюда, они подойдут.

2. Нам известна сумма этих чисел. Например, a+b=64383

3. Допустим получили систему из уравнений(допустим такую, не смотрите на левую часть, почему такая, не важно сейчас, и не важно, что возможно, эта система не имеет единственного решения).

Допустим она такая. Нам важна сейчас только правая часть
Стартовый вектор очевидно равен:


Мне нужно найти все возможные r^i. Сегодня рассуждал, и пришёл к выводу, что лучше всего, прочитать мысли Кнута о деревеьях, и реализовать задуманное с помощью них. К этому я пришёл после того, когда нарисовал нижеследующее.
Но возможно, я ошибаюсь, потому и спрашиваю у вас. Это важная часть, но она не влияет на реализацию главной идеи, потому спрашиваю у вас. Подскажите пожалуйста, возможно я в чём-то ошибаюсь, и моя подзадача решается проще ?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.08.2014, 08:42
    #38728667
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение одной задачи. Вопросы по программному коду и способам реализации.
А как насчет такого случая
Код: plaintext
1.
789 + 987 = 1776


По условию задачи подходит, но в твою систему уравнений не вписывается.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.08.2014, 08:49
    #38728671
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение одной задачи. Вопросы по программному коду и способам реализации.
Дмитрий, вы всё верно сказали :) Тут, это меня не интересует, как и тот факт, что система может иметь бесконечное число решений. Интересует лишь возможные правые части. Пусть сумма имеет порядок такой же как у операндов
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.08.2014, 08:59
    #38728676
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение одной задачи. Вопросы по программному коду и способам реализации.
SashaMercuryПусть сумма имеет порядок такой же как у операндов
Код: plaintext
1.
392 + 239 = 631


Порядок одинаковый )))

Начни с того что сначала надо четко задачу сформулировать. Может ты сам ее и понимаешь, но телепатов тут нет, твои мысли никто не читает.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.08.2014, 09:38
    #38728709
egorych
egorych
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение одной задачи. Вопросы по программному коду и способам реализации.
SashaMercury,
может, в программирование, а? С++ то тут причём?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.08.2014, 10:29
    #38728744
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение одной задачи. Вопросы по программному коду и способам реализации.
Нет, это именно С/С++. Потому что я уверен что эту задачу (основную задачу), можно решить красивее на этом языке. Плюс у меня уже появились вопросы по моему коду на Си, но я не могу спросить, потому что все поймёт какую задачу (основную) я решаю.

Dima_T392 + 239 = 631

Тут всё ок, разве этот пример не подходит под мое описание ? Можно, по другому сказать, что множества разрядов двух чисел равны. Порядок трёх чисел одинаковый. Вроде бы максимально просто объяснил..
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.08.2014, 10:29
    #38728746
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение одной задачи. Вопросы по программному коду и способам реализации.
потому что все поймут*
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.08.2014, 10:55
    #38728783
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение одной задачи. Вопросы по программному коду и способам реализации.
SashaMercuryDima_T392 + 239 = 631

Тут всё ок, разве этот пример не подходит под мое описание ?
Как я понял должна выполнятся система уравнений:
Код: plaintext
1.
2.
3.
3 + 2 = 6
9 + 3 = 3
2 + 9 = 1
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.08.2014, 11:24
    #38728819
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение одной задачи. Вопросы по программному коду и способам реализации.
Вот ! Мне нужно найти все возможные правые части:
Вот что в вашем примере получается:


631 это только стартовый вектор

Вот такие цепочки я хочу получить с помощью этого дерева:
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.08.2014, 13:31
    #38728994
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение одной задачи. Вопросы по программному коду и способам реализации.
SashaMercuryУже второй день решаю одну задачу, я думаю она покажется вам интересной
Ты не поверишь. Вообще ниразу неинересно.
И тема С++ не прослеживается.

Может обсудим это в Программировании или Вопрос-Ответ?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.08.2014, 01:53
    #38729661
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение одной задачи. Вопросы по программному коду и способам реализации.
maytonSashaMercuryУже второй день решаю одну задачу, я думаю она покажется вам интересной
Ты не поверишь. Вообще ниразу неинересно.
И тема С++ не прослеживается.

Может обсудим это в Программировании или Вопрос-Ответ?

Я не считаю что этот топик нужно переносить. Но если администрация раздела C/C++ считает нужным что-либо сделать с этой темой, моё мнение не играет существенной роли
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.08.2014, 03:06
    #38729673
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение одной задачи. Вопросы по программному коду и способам реализации.
Модератор: Оффтопик поскипан
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.08.2014, 06:19
    #38729683
SashaMercury
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.
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.
//на входе реверс числа 
int* create_rCloud(const char* s)
{
	int p = strlen(s);
	int num_v = 1 << (p - 1);//количество вариантов правой части 2^n-1
	int* r = (int*)malloc(sizeof(int)*p*num_v);//буфер в котором хранятся все варианты векторов правой части
	
	for (int i = 0; i < p; ++i)//цикл по i-ым позициям в векторах 
	{
		if (i == 0)//рассматривается первый разряд числа
		{
			int frequency = 1 << (p - 1 - i - 1);
			int t[2];
			t[0] = s[i] - '0';
			t[1] = s[i] + 10 - '0';

			int j = 0; 
			for (int k = 0; k < 2; ++k)
			{
				for (int l = 0; l < frequency; ++l)
				{
					r[j*p + i] = t[k];
					++j;
				}
			}
		}

		if (i >= 0 && i < p - 1)//если рассматривается не первый, и не последний разряд числа
		{
			int t[4];//все возможные варианты на этой позиции
			t[0] = s[i] - '0';
			t[1] = s[i] + 10 - '0';
			t[2] = s[i] - 1 - '0';
			t[3] = s[i] + 10 - 1 - '0';
			int frequency = 1 << (p - 1 - i - 1);//частота с которой встречается каждый элемент t[k],k=0..3

			int j = 0; 
			while (j < num_v) //цикл по всем векторам. обращение к элементу вектора r[j*p+i]
			{
				for (int k = 0; k < 4 && j < num_v; ++k)
				{
					for (int l = 0; l < frequency; ++l)
					{
						r[j*p + i] = t[k];
						++j;
					}
				}
			}
		}
		if (i == p - 1)//рассматривается последний разряд числа
		{
			int t[2];
			t[0] = s[i] - '0';
			t[1] = s[i] - 1 - '0';

			int j = 0;
			while (j < num_v) //цикл по всем векторам. обращение к элементу вектора r[j*p+i]
			{
				for (int k = 0; k < 2; ++k)
				{
					r[j*p + i] = t[k];
					++j;
				}
			}
		}
			
	}
	return r;
}



Пока храню все значения, даже если получаются отрицательные. Позже оптимизирую
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.08.2014, 06:27
    #38729684
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение одной задачи. Вопросы по программному коду и способам реализации.
Дмитрий, вот ваш пример

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
	char* s = "136";
	int* r = create_rCloud(s);

	int p = strlen(s);
	int num_v = 1 << (p - 1);//количество вариантов правой части 2^n-1
	
	for (int i = 0; i < num_v; ++i)
	{
		for (int j = 0; j < p; ++j)
		{
			printf("%2i ", r[i*p + j]);
		}
		printf("\n");
	}
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.08.2014, 07:42
    #38729695
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение одной задачи. Вопросы по программному коду и способам реализации.
SashaMercuryГотово, и работает

Отлично
SashaMercuryДмитрий, вот ваш пример ...

Теперь объясни что за магические числа у тебя получились. Я так и не понял чего ты считал.
Например как (11,12,5) связано с (1,3,6).
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.08.2014, 08:45
    #38729717
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение одной задачи. Вопросы по программному коду и способам реализации.
Не ругайтесь, что я написал так. Просто глаза уже очень устали за сегодня, и я бы ошибся если бы печатал. Очень близок к решению всей задачи, знаю что нужно, но не мог оторваться 4 часа от монитора
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.08.2014, 09:41
    #38729753
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение одной задачи. Вопросы по программному коду и способам реализации.
Понял наконец-то твой хитрый алгоритм :)

Тогда не доделал ты свою прогу.
Например исходные данные
Код: plaintext
1.
197 + 719 = 916


как понимаю должно получиться
Код: plaintext
1.
8, 10, 16


твоя прога выдает
Код: plaintext
1.
2.
3.
4.
 9  1  6
 9 11  5
19  0  6
19 10  5



PS чтобы скриншоты черных окошек не вставлять: кликаешь в левый верхний угол (иконка "c:\") - изменить - пометить - держишь кнопку на мышке и выделяешь нужный прямоугольник - Enter. Выделенный кусок в буфере обмена. Ctrl+V вставить в нужное место.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.08.2014, 10:00
    #38729774
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение одной задачи. Вопросы по программному коду и способам реализации.
Спасибо за совет )
А вы реверсом ввели число ?)))
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.08.2014, 10:03
    #38729780
Basil A. Sidorov
Basil A. Sidorov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение одной задачи. Вопросы по программному коду и способам реализации.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.08.2014, 10:08
    #38729784
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение одной задачи. Вопросы по программному коду и способам реализации.
SashaMercuryА вы реверсом ввели число ?)))
Нет, предупреждать надо, реверсом правильно работает.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.08.2014, 11:35
    #38729953
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение одной задачи. Вопросы по программному коду и способам реализации.
в самом начале сделал комментарий к функции ;)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.08.2014, 14:27
    #38730346
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение одной задачи. Вопросы по программному коду и способам реализации.
Что это?
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
while (j < num_v) //цикл по всем векторам. обращение к элементу вектора r[j*p+i]
			{
				for (int k = 0; k < 4 && j < num_v; ++k)
				{
					for (int l = 0; l < frequency; ++l)
					{
						r[j*p + i] = t[k];
						++j;
					}
				}
			}


Зачем j<num_v проверяется дважды? Для надёжности? Или учитываешь шум электронов в кристаллической решётке?

Или просто лажанулся?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.08.2014, 16:38
    #38730665
Anatoly Moskovsky
Anatoly Moskovsky
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение одной задачи. Вопросы по программному коду и способам реализации.
mayton,

Для надежности обычно дважды присваивают :)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.08.2014, 16:47
    #38730693
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение одной задачи. Вопросы по программному коду и способам реализации.
В авиации я слышал системы управления не "удваивают" а "утраивают".
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.08.2014, 20:09
    #38730926
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение одной задачи. Вопросы по программному коду и способам реализации.
SashaMercuryв самом начале сделал комментарий к функции ;)
Виноват, не заметил. Могу сказать что задачу ты хоть и решил, но сделал это на треть, т.е. придумал алгоритм и реализовал, вторые две трети - оформить его в понятный всем вид и сделать легкоиспользуемым, это нудно и неинтересно, но таковы издежки нашей профессии. В итоге должно быть что-то целое, т.е. законченное и понятное.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
  1  все
Форумы / C++ [игнор отключен] [закрыт для гостей] / Решение одной задачи. Вопросы по программному коду и способам реализации. / 25 сообщений из 41, страница 1 из 2
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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