ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / Мешки и кирпичи. Проблемы в реализации
5 сообщений из 30, страница 2 из 2
  2  все
Мешки и кирпичи. Проблемы в реализации
    #38669972
Фотография 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.
	//Максимальный размер результирующего набора комбинаций
	int res_pow = 1;
	for (int i = 0; i < k; i++)
	{
		res_pow *= bags[i].pow_comb;
	}
	res_pow *= k;
	int* res = (int*)malloc(sizeof(int)*res_pow);
	//Зануляю результирующий набор комбинаций
	for (int i = 0; i < res_pow; i++)
	{
		*(res + i) = 0;
	}
	
	//Временный массив, на него буду умножать
	int temp_pow = k*bags[0].pow_comb;
	int* temp[k];
	temp[0] = (int*)malloc(sizeof(int)*temp_pow);
	for (int i = 0; i < temp_pow; i++)
	{
		*(temp[0] + i) = 0;
	}
	for (int i = 0; i < bags[0].pow_comb; i++)
	{
		*(temp[0] + k*i) = bags[0].comb[i];
	}


	int cur=0;//Текущая позиция k байт в res
	int interval_pow = 0;//Реальная длина интервала
	for (int i = 0; i < k; i++)//Иду по мешкам
	{
		for (int j = 0; j < bags[i].pow_comb; j++)//Иду по всем комбинациям для мешка
		{
			for (int s = 0; s < temp_pow / k; s++)//Иду по всем интервалам в temp. 1 интервал имеет длину k
			{
				int t = 0;
				//Захожу в интервал
				for (int l = 0; l < k; l++)//уже вошёл в интервал
				{
					t += *(temp[i] + s*k + l)&bags[i].comb[j];
				}
				if (t == 0)//Если нет пересечений
				{
					printf(" \n ok");
					for (int w = 0; w < k; w++)
					{
						*(res + cur*k + w) = *(temp[i] + s*k + w);
					}
					*(res + cur*k + interval_pow + 1) = bags[i].comb[j];
					cur++;
				}
			}
		}
		interval_pow++;
		temp_pow = cur*k;
		temp[i + 1] = (int*)malloc(sizeof(int)*temp_pow);
		for (int p = 0; p < temp_pow; p++)
		{
			*(temp[i+1] + p) = *(res + p);
		}
		cur = 0;

	}



Тут скорее всего неправильная работа с памятью. В этом участке кода.
...
Рейтинг: 0 / 0
16.06.2014, 06:59
| Ответить | Цитировать | Написать  
Мешки и кирпичи. Проблемы в реализации
    #38669973
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
А, можно . С помощью free . Я думал что free освобождает всю память в программе. Сейчас почитаю документацию по ней.
...
Рейтинг: 0 / 0
16.06.2014, 07:00
| Ответить | Цитировать | Написать  
Мешки и кирпичи. Проблемы в реализации
    #38669989
Фотография 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.
70.
71.
72.
73.
74.
	//Поиск уникального пересечения

	//максимальный размер результирующего набора комбинаций
	int res_pow = 1;
	int res_len = 0;//длина де-факто
	for (int i = 0; i < k; i++)
	{
		res_pow *= bags[i].pow_comb;
	}
	res_pow *= k;
	int* res = (int*)malloc(sizeof(int)*res_pow);//в этом массиве будут храниться результирующие наборы
	//зануляю результирующий набор комбинаций
	for (int i = 0; i < res_pow; i++)
	{
		*(res + i) = 0;
	}
	


	//временный массив, на него буду умножать
	int* temp;
	int temp_pow = k*bags[0].pow_comb;
	temp = (int*)malloc(sizeof(int)*temp_pow);
	for (int i = 0; i < temp_pow; i++)
	{
		*(temp + i) = 0;
	}

	for (int i = 0; i < bags[0].pow_comb; i++)
	{
		*(temp + k*i) = bags[0].comb[i];
	}



	//основной цикл
	int cur=0;//текущая позиция k байт в res
	int interval_pow = 0;//реальная длина интервала
	for (int i = 0; i < k; i++)//иду по мешкам
	{
		for (int j = 0; j < bags[i].pow_comb; j++)//иду по всем комбинациям для мешка
		{
			for (int s = 0; s < temp_pow / k; s++)//иду по всем интервалам в temp. 1 интервал имеет длину k
			{
				unsigned int t = 0;
				//захожу в интервал
				for (int l = 0; l < k; l++)//уже вошёл в интервал
				{
					t += *(temp + s*k + l)&bags[i].comb[j];//Тут всегда будет число больше либо равное 0 ?
				}
				if (t == 0)//Если нет пересечений
				{
					printf(" \n ok");
					for (int w = 0; w < k; w++)
					{
						*(res + cur*k + w) = *(temp + s*k + w);
					}
					*(res + cur*k + interval_pow + 1) = bags[i].comb[j];
					cur++;
				}
			}
		}
		interval_pow++;
		temp_pow = cur*k;
		free(temp);
		temp = (int*)malloc(sizeof(int)*temp_pow);
		for (int p = 0; p < temp_pow; p++)
		{
			*(temp + p) = *(res + p);
		}
		res_len = cur;
		cur = 0;

	}
...
Рейтинг: 0 / 0
16.06.2014, 07:53
| Ответить | Цитировать | Написать  
Мешки и кирпичи. Проблемы в реализации
    #38670008
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Работает C:

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

const char k = 3;//количество мешков
const char n = 10;//количество кирпичей

struct bag
{
	unsigned int w;//вес
	unsigned int pow_comb;//настоящая мощность массива подходящих комбинаций
	int comb[1 << n];//в данном массиве будут храниться все возможные комбинации
} bags[k];

struct brick
{
	unsigned int w;//вес
} bricks[n];

void view_combination_break(int bag, int combination, int count_breaks)
{
	printf("\nindexes breaks for bag %i = have integer = %i ====== ", bag, combination);
	for (int i = 0; i<count_breaks; i++)
	{
		if ((combination >> i) & 1 != 0)
		{
			printf(" %i ", i);
		}
	}
	printf("\n");
}

int main(int argc, char** argv)
{
	//Инициализация массива мешков и массива кирпичей
	printf("Initializing array bags\n");
	for (int i = 0; i<k; i++)
	{
		printf("bag %i:", i);
		scanf("%u", &bags[i].w);
		bags[i].pow_comb = 0;//можно ли это сделать при объявлении структуры ?
	}
	printf("\n Initializing array bricks\n");
	for (int i = 0; i<n; i++)
	{
		printf("bricks %i:", i);
		scanf("%u", &bricks[i].w);
	}

	//Ищу все возможные комбинации для каждого мешка
	for (int i = 0; i<k; i++)//Цикл по мешкам bags[i]
	{
		for (int j = 0; j <= (1 << n); j++)//цикл по комбинации множеств кирпичей j
		{
			int temp_res = 0;
			for (int s = 0; s<n; s++)//суммирую массу текущей комбинации кирпичей
			{
				temp_res += (1 & (j >> s))*(bricks[s].w);
			}
			if (bags[i].w == temp_res)//Если сумма текущей комбинации кирпичей j равна массе текущего мешка i
			{
				bags[i].comb[bags[i].pow_comb] = j;
				bags[i].pow_comb++;
			}
		}

	}
	//Вывод на экран всех возможных комбинаций для каждого мешка
	for (int i = 0; i<k; i++)
	{
		for (int j = 0; j<bags[i].pow_comb; j++)
		{
			view_combination_break(i, bags[i].comb[j], n);
		}
	}




	//Поиск уникального пересечения

	//максимальный размер результирующего набора комбинаций
	int res_pow = 1;
	int res_len = 0;//длина де-факто
	for (int i = 0; i < k; i++)
	{
		res_pow *= bags[i].pow_comb;
	}
	res_pow *= k;
	int* res = (int*)malloc(sizeof(int)*res_pow);//в этом массиве будут храниться результирующие наборы
	//зануляю результирующий набор комбинаций
	for (int i = 0; i < res_pow; i++)
	{
		*(res + i) = 0;
	}
	


	//временный массив, на него буду умножать
	int* temp;
	int temp_pow = k*bags[0].pow_comb;
	temp = (int*)malloc(sizeof(int)*temp_pow);
	for (int i = 0; i < temp_pow; i++)
	{
		*(temp + i) = 0;
	}

	for (int i = 0; i < bags[0].pow_comb; i++)
	{
		*(temp + k*i) = bags[0].comb[i];
	}

	/*
	for (int i = 0; i < temp_pow; i++)
	{
		printf("\n%i", *(temp + i));
	}
	printf("\n \n \n ");
	*/



	//основной цикл
	int cur=0;//текущая позиция k байт в res
	int interval_pow = 0;//реальная длина интервала
	for (int i = 1; i < k; i++)//иду по мешкам
	{
		for (int j = 0; j < bags[i].pow_comb; j++)//иду по всем комбинациям для мешка
		{
			for (int s = 0; s < temp_pow / k; s++)//иду по всем интервалам в temp. 1 интервал имеет длину k
			{
				int t = 0;
				//захожу в интервал
				for (int l = 0; l < k; l++)//уже вошёл в интервал
				{
					t += *(temp + s*k + l)&bags[i].comb[j];//Тут всегда будет число больше либо равное 0 ?
				}
				if (t == 0)//Если нет пересечений
				{
					//printf(" \n ok");
					for (int w = 0; w < k; w++)
					{
						*(res + cur*k + w) = *(temp + s*k + w);
					}
					*(res + cur*k + interval_pow + 1) = bags[i].comb[j];
					cur++;
				}
			}
		}
		interval_pow++;
		temp_pow = cur*k;
		free(temp);
		temp = (int*)malloc(sizeof(int)*temp_pow);
		for (int p = 0; p < temp_pow; p++)
		{
			*(temp + p) = *(res + p);
		}
		res_len = cur;
		cur = 0;

	}




	for (int i = 0; i < res_len; i++)
	{
		printf("\n");
		for (int j = 0; j < k; j++)
		{
			printf("%i ", *(res + k*i + j));
		}
		printf("\n");
	}

	if (res_len == 0)
	{
		printf(" \n no options \n");
	}

	return 0;
}
...
Рейтинг: 0 / 0
16.06.2014, 08:49
| Ответить | Цитировать | Написать  
Мешки и кирпичи. Проблемы в реализации
    #38670070
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Да, тут вес каждого кирпича должен быть уникален. Но это легко исправить. Главное, что этот алгоритм работает.
Я уже придумал два проще этого.
...
Рейтинг: 0 / 0
16.06.2014, 10:33
| Ответить | Цитировать | Написать  
5 сообщений из 30, страница 2 из 2
  2  все
Форумы / C++ [игнор отключен] [закрыт для гостей] / Мешки и кирпичи. Проблемы в реализации
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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