powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / C++ [игнор отключен] [закрыт для гостей] / Решение одной задачи. Вопросы по программному коду и способам реализации.
16 сообщений из 41, страница 2 из 2
Решение одной задачи. Вопросы по программному коду и способам реализации.
    #38731059
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Дмитрий, вы совершенно правы(кроме легкоиспользуемости, её легко использовать, реверс это не проблема). Но передо мной сейчас стоит большая задача, и я уже очень близок к её решению, очень близок(правда на это может уйти два дня). Допишу это сообщение, и буду оптимизировать совсем другой алгоритм, где rCloud всего лишь вспомогательная часть. Когда я напишу программу, и она будет работать везде где должна работать, я займусь оптимизацией того, что уже протестировано (и эта функция тоже).

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

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
Решение одной задачи. Вопросы по программному коду и способам реализации.
    #38732296
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я сдал её ребята !!!!! Всего её сдали 9 человек из 30.000 участников :)

После обеда все расскажу !
...
Рейтинг: 0 / 0
Решение одной задачи. Вопросы по программному коду и способам реализации.
    #38732312
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Мне хотелось попасть в топ 10 при решении задачи, но при решении задачи уже решенной тысячами других людей, и использующих cout вместо printf(уже экономия в символах), и использовании кучи define (мне это не очень нравится), это затруднительно. Потому, я подумал, что мне нужно решить задачу, решенную менее чем 10ю пользователями. Собственно вот она .
По простому она звучит так:

где sh(x,k) это циклический сдвиг влево на k позиций.

Думаю, что могу рассказать без спойлеров как я её решал, ибо с большой долей вероятности существует более простое решение(собственно буду рад узнать его). Намеренно не гуглил (по классическому совету Анатолия), не искал методы дешифрации, или smth else.


Для меня эта задача выглядит как система линейных диофантовых уравнений, с ограничениями на значение вектора решения. Если бы это была система ДУ, было бы понятнее, но с система Диоф. ур. я дел никогда не имел. Знал только что это. Гуглить про них тоже не стал, хотелось решить самому.(впрочем сейчас полчаса поискал, уже после решения, ни одной нормальной русской статьи не нашел).

Вот основные типы данных с которыми я работал в программе:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
//уравнение в формате a_op_i[0]+a_op_i[1]=sum
struct Equation
{
	int ind[2];//индексы в сумме
	int sum;//сумма
};

//облако уравнений
struct CloudEquations
{
	int p;//количество уравнений CONST
	struct Equation* eqs;// = NULL уравнений
	int* solve;// = NULL решения; если решение на найдено, происходит инициализация значениями '-1';solve[i]>=0
	int state;//состояние облака
};



//закомментировал =NULL потому что система не компилировала эти моменты.

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

Код: 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.
struct CloudEquations* create_ceqs(char* y, int shift, int p)
{
//формирование облака уравнений. на входе массив символов '0'<=c<='9' и сдвиг

	struct CloudEquations* c = (struct CloudEquations*)malloc(sizeof(struct CloudEquations));
	int n = p - 1;//n=rounding_less(lgy)
	int k = shift;
	c->p = p; //1. CONST количество уравнений
	//2. выделяю память и создаю систему уравнений
	c->eqs = (struct Equation*)malloc(sizeof(struct Equation)*p);
	for (int i = 0; i < p; ++i)
	{
		c->eqs[i].ind[0] = i;
		c->eqs[i].ind[1] = (i < k) ? n - k + 1 + i : i - k;
	}
	//3. выделяю память и инициализирую массив решений
	c->solve = (int*)malloc(sizeof(int)*p);
	for (int i = 0; i < p; ++i)
	{
		c->solve[i] = -1;
	}
	//4. установка состояния облака; -1 облако не разрешено; 1 разрешено; 
	c->state = -1;
	return c;
}



И вот функция просмотра
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
int view_ceqs(struct CloudEquations* c)
{
	printf("START VIEW\n");
	printf("CONST p/The number of equations = %i\n", c->p);
	printf("\nThe system of equations:\n");
	for (int i = 0; i < c->p; ++i)
	{
		printf("x%i + x%i = %i\n", c->eqs[i].ind[0], c->eqs[i].ind[1], c->eqs[i].sum);
	}
	printf("\nSolution of the system:\n");
	for (int i = 0; i < c->p; ++i)
	{
		printf("x%i = %i\n", i, c->solve[i]);
	}
	printf("State of clouds = %i\n", c->state);
	printf("END VIEW\n");
	return 1;
}



Далее, пусть например на входе будет 7251376
Мы получим следующее множество систем диофантовых уравнений


и ещё одно множество должно быть в общем случае, тут его нет. Случай такой:в x разрядов меньше чем в y. Такой пример приводил Дмитрий (эта программа и такое решает)

Как я предлагаю её решать. Мы все знаем что вектор решения должен состоять из целых числе в диапазоне от 0 до 9. Мне показалось разумным делать уколы этому облаку, и проверять, подходят ли эти уколы ему, или нет. Рекурсивная функция вводит значения от 0 до 9, и смотрит что получится. Думаю всем уже понятно как она работает. Вот код. Кстати, код мне не нравится,из-за goto, и вообще, его нужно оптимизировать. Это очевидно.

Код: 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.
//Рекурсивные инъекции в облако уравнений
int injection_intoClouudEquations(struct CloudEquations* c)
{
	for (int s = 0; s < 10 && c->state < 0; ++s)//цикл по видам инъекций
	{
		//массив не найденных решений
		int* f0 = (int*)malloc(sizeof(int)*c->p);
		for (int i = 0; i < c->p; ++i)
			f0[i] = (c->solve[i] == -1) ? -1 : 0;

		//нахожу индекс для укола
		int ind_s = 0;
		while (c->solve[ind_s] >= 0) 
			++ind_s;

		c->solve[ind_s] = s;//УКОЛ (установка стартового значения)

		int count;
		while (c->state<0) //пока не найдены все решения
		{
			int isOk = 0;
			count = c->p;
			for (int i = 0; i < c->p; ++i)//цикл по уравнениям
			{
				int i0 = c->eqs[i].ind[0];//текущий 0 индекс
				int i1 = c->eqs[i].ind[1];//текущий 1 индекс
				bool t0 = (c->solve[i0] == -1);//решение не найдено
				bool t1 = (c->solve[i1] == -1);//решение не найдено
				if (t0 + t1 == 1)//одно решение найдено, другое не найдено
				{
					++isOk;
					int t2 = (t0 == 1) ? i0 : i1;//в t2 индекс не найденного значения
					c->solve[t2] = c->eqs[i].sum - c->solve[i0 + i1 - t2];

					if (c->solve[t2]<0 || c->solve[t2]>9 || c->solve[c->p - 1] == 0)
					{
						goto label_end;
					}
				}
				else if (t0 + t1 == 0 && (c->solve[c->eqs[i].ind[0]] + c->solve[c->eqs[i].ind[1]] != c->eqs[i].sum))//сумма найденных решений не равна правой части
				{
					goto label_end;
				}
				else if (t0 + t1 == 0)
				{
					--count;
				}
			}//закончился цикл по уравнениям


			if (count == 0)
			{
				c->state = 1;
				free(f0);
				return 1;
			}

			if (isOk == 0 && count != 0)
			{
				//printf("\nen\n");
				int t = injection_intoClouudEquations(c);
				if (t == -1)
				{
					break;
				}
			}

		}

		if (c->state < 0)
		{

		label_end:;
			count = c->p;
			//Зануляю те позиции, чтобы были изменены уколом в позицию
			for (int i = 0; i < c->p; ++i)
			{
				f0[i] == -1 ? c->solve[i] = -1 : false;
			}
			free(f0);
		}
	}//завершается цикл по видам инъекций
	return -1;
}



Функцию получающую правые вектора я представлял ранее. Файл также прикрепляю к этому сообщению.

Буду рад услышать комментарии по предложенному методу, и более простое решение :-)
...
Рейтинг: 0 / 0
Решение одной задачи. Вопросы по программному коду и способам реализации.
    #38732404
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryЯ сдал её ребята !!!!! Всего её сдали 9 человек из 30.000 участников :)
Позорище Самое плохое время. Самый большой размер. Самая большая занимаемая память.

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

Да и я не мог не показать, я ведь всем пообещал что до пятницы сделаю и покажу, вчера 8 часов писал и отлаживал.
...
Рейтинг: 0 / 0
Решение одной задачи. Вопросы по программному коду и способам реализации.
    #38732419
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
И вообще три товарища выше меня сдали практически в одно и тоже время, это подозрительно :)
...
Рейтинг: 0 / 0
Решение одной задачи. Вопросы по программному коду и способам реализации.
    #38732428
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Когда пишешь взаимоиключающие условия - не повторяйся.

Вместо

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
                        if (count == 0)
			{
				c->state = 1;
				free(f0);
				return 1;
			}

			if (isOk == 0 && count != 0)
			{
				//printf("\nen\n");
				int t = injection_intoClouudEquations(c);
				if (t == -1)
				{
					break;
				}
			}



лучше писать так

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
                        if (count == 0)
			{
				c->state = 1;
				free(f0);
				return 1;
			}

                        else if (isOk == 0)
			{
				//printf("\nen\n");
				int t = injection_intoClouudEquations(c);
				if (t == -1)
				{
					break;
				}
			}


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

Сейчас занимаюсь общей оптимизацией. Хочу вынести функции просмотра в отдельный файл. Они не несут основной функционал, и отвлекают от общей картины. Создал файл view.cpp. В нем попытался подключить основной файл, и вставить функции просмотра, но действие корректно не происходит

Код: 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.
#include <stdio.h>
 #include <0655.cpp>

int view_ceqs(struct CloudEquations* c)
{
	printf("START VIEW\n");
	printf("CONST p/The number of equations = %i\n", c->p);
	printf("\nThe system of equations:\n");
	for (int i = 0; i < c->p; ++i)
	{
		printf("x%i + x%i = %i\n", c->eqs[i].ind[0], c->eqs[i].ind[1], c->eqs[i].sum);
	}
	printf("\nSolution of the system:\n");
	for (int i = 0; i < c->p; ++i)
	{
		printf("x%i = %i\n", i, c->solve[i]);
	}
	printf("State of clouds = %i\n", c->state);
	printf("END VIEW\n");
	return 1;
}

int view_rCloud(const char* r, const char* s, int p)
{
	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");
	}
	printf("\n");
	return 1;
}



Пробовал в одинарные кавычки, не помогло. Стоит ли выносить функции просмотра в отдельный файл ? Тут, думаю, нужно почитать про препроцессор чтобы понять как это сделать ?

PS
Думал повторно описать структуру в этом файле, но так делать не стоит. Хотя в больших проектах, наверное структуры выносят в отдельный файл ? (это предположение)
...
Рейтинг: 0 / 0
Решение одной задачи. Вопросы по программному коду и способам реализации.
    #38733771
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryСоздал файл view.cpp. В нем попытался подключить основной файл
Код: plaintext
1.
 #include <0655.cpp>


Хорошо что не #include <666.cpp>

.cpp файлы, и вообще файлы содержащие тела функций не включают через include а компилируют отдельно и потом полученные объектные модули каждого указывают при сборке (линковке) программы.
Подробнее - в любом учебнике по С.
SashaMercuryПробовал в одинарные кавычки, не помогло. Стоит ли выносить функции просмотра в отдельный файл ? Тут, думаю, нужно почитать про препроцессор чтобы понять как это сделать ?
Сначала почитайте про препроцессор. Давно пора было это сделать.
Вообще вопросы поднятые в этом посте должны были быть вами разобраны в первую неделю изучения С.
SashaMercuryДумал повторно описать структуру в этом файле, но так делать не стоит. Хотя в больших проектах, наверное структуры выносят в отдельный файл ? (это предположение)
Структуры и прототипы функций и прочие объявления обычно описывают в файлах с расширением .h и включают в те .cpp где они используются.
При этом есть ряд нюансов таких как защита от повторного включения и пр. - опять же это все есть в любом учебнике.
...
Рейтинг: 0 / 0
Решение одной задачи. Вопросы по программному коду и способам реализации.
    #38733772
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Хорошо, спасибо :)
...
Рейтинг: 0 / 0
Решение одной задачи. Вопросы по программному коду и способам реализации.
    #38733773
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Тут получится странная ситуация. В файле а.cpp у меня содержится описание структуры основные методы, и допустим вызов функции просмотра. А в фале b.cpp у меня содержатся методы для просмотра состояния структур. То есть для компиляции файла b.cpp мне нужно чтобы уже был собран файл а.cpp(чтобы была видна структура из файла а.cpp в файле b.cpp), а для сборки файла а.cpp (в котором содержится вызов функции просмотра из файла b.cpp) мне нужны действия противоположные первым.

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

ЗЫ. В С не принято расширение .cpp. Более того при таком расширении компилятор будет считать что программа на С++.
Для С используйте .c
...
Рейтинг: 0 / 0
Решение одной задачи. Вопросы по программному коду и способам реализации.
    #38733812
Фотография 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.
char* create_rCloud(const char* s, char* r, int mode)
{
	int p = (mode == STANDART) ? strlen(s) : strlen(s) - 1;
	int num_v = 1 << (p - 1);//количество вариантов правой части 2^n-1

	int t[4];//все возможные варианты на этой позиции
	for (int i = 0; i < p; ++i)//цикл по i-ым позициям в векторах 
	{
		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]
		{
			if (i == 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)//если рассматривается не первый, и не последний разряд числа
			{
				for (int k = 0; k < 4; ++k)//&& j < num_v
				{
					for (int l = 0; l < frequency; ++l)
					{
						r[j*p + i] = t[k];
						++j;
					}
				}
			}
			if (i == p - 1)//рассматривается последний разряд числа
			{
				if (mode == STANDART)
				{
					t[1] = s[i] - 1 - '0';
				}
				else
				{
					t[0] = s[i] - '0' + 10 * (s[i + 1] - '0');
					t[1] = s[i] - 1 - '0' + 10 * (s[i + 1] - '0');
				}
				for (int k = 0; k < 2; ++k)
				{
					r[j*p + i] = t[k];
					++j;
				}
			}
		}
	}

	return r;
}



mode показывает есть ли перенос в старшем разряде. Простыми словами, если mode=1, то количество разрядов суммы равно количество разрядов полученного числа, в противном случае, количество разрядов операндов суммы на 1 меньше.

Как работает этот алгоритм? возьмём число 64383. Рассмотрю вариант без увеличения разрядности суммы. Прикрепил картинку. По ней можно легко понять алгоритм
...
Рейтинг: 0 / 0
Решение одной задачи. Вопросы по программному коду и способам реализации.
    #38733813
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Anatoly Moskovsky , запомнил. Спасибо :)
...
Рейтинг: 0 / 0
Решение одной задачи. Вопросы по программному коду и способам реализации.
    #38735598
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Проблема с памятью решена. Эти 5.4 Мб появлялись из-за больших трат все возможны варианты правой части системы уравнений. Мне не нужно хранить все элементы правой части, легко можно получить следующий правый вектор-столбец исходя из текущего (исходя из индексов вариантов текущих значений).

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
//на входе реверс индексов
char* get_next_r(char* in)
{
	int p = strlen(in);
	int t = 0;
	//отдельная проверка первого индекса
	int i = 0;
	(in[i] == 0) ? (in[i] = 1, t += 1) : in[i] = 0;
	
	i += 1;
	while (t<2)
	{
		in[i] += 1;
		(in[i] < 4) ? t += 1 : in[i] = 0;
		i += 1;
	}
	return in;
}



А вот так можно проверить этот код, правда тут без реверса, но это детали. Решаемые.


Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
	char s1[5] = { 0, 0, 0, 0, 0 };
	for (int i = 0; i < 15; ++i)
	{
		get_next_r(s1);
		for (int i = 0; i < 5; ++i)
			printf("%i", s1[i]);

		printf("\n");
	}



Рисунок ниже отлично поясняет как этот код работает
...
Рейтинг: 0 / 0
Решение одной задачи. Вопросы по программному коду и способам реализации.
    #38735599
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
...
Рейтинг: 0 / 0
16 сообщений из 41, страница 2 из 2
Форумы / C++ [игнор отключен] [закрыт для гостей] / Решение одной задачи. Вопросы по программному коду и способам реализации.
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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