ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Поиск любых сочетаний из К чисел
25 сообщений из 206, страница 4 из 9
  4  все
Поиск любых сочетаний из К чисел
    #39709901
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
maytonGennadiy Usov,
JavaScript не умеет возводить в степень так как вы описали.
С одной стороны похвально что вы пытаетесь помочь. С другой стороны это выглядит как медвежья услуга.
И помогли и запутали.Тогда по другому:
Код: javascript
1.
2.
3.
var K1=1;
for(var i = 1; i <= (K-3); i++) K1=K1*2;
К1=К1-1;
...
Рейтинг: 0 / 0
28.09.2018, 15:14
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39710067
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Dima TGennadiy UsovПри К = 3 должно получиться 100, 010, 001.А при К = 4 добавится 1000, 0100, 0010, 0001. Так ?
Если так то это К вариантов, а не 2^(K-1)
И показанное это степени двойки, если рассматривать эти числа как двоичные, т.е.
Код: sql
1.
2.
3.
4.
2^0 = 0b0001 = 1
2^1 = 0b0010 = 2
2^2 = 0b0100 = 4
2^3 = 0b1000 = 8

А здесь сочетания для К=4
Код: javascript
1.
2.
3.
4.
5.
6.
7.
0	0	0	1
0 	0 	1	0 
0 	1	0 	0 
1	0 	0 	0 
0 	0 	1	1
0 	1	0 	1
1	0  	0 	1
...
Рейтинг: 0 / 0
28.09.2018, 18:09
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39710214
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Gennadiy Usov[/src]А здесь сочетания для К=4
Код: javascript
1.
2.
3.
4.
5.
6.
7.
0	0	0	1
0 	0 	1	0 
0 	1	0 	0 
1	0 	0 	0 
0 	0 	1	1
0 	1	0 	1
1	0  	0 	1

[/quot]Кстати, последнее сообщение показывает: если набирать операторы в таблице EXCEL в разных колонках, то табуляция сама получится.
...
Рейтинг: 0 / 0
29.09.2018, 06:04
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39710229
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Это текст, подготовленный в таблице EXCEL.

Постарался большую часть определения сочетаний "запрятать" в процедуру.
Код: javascript
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.
// K – количество чисел (объектов).					
var P = new Array(K+1);					
for(var i = 1; i <= K; i++) P[i]=0;					
					
var K1=1;					
for(var i = 1; i <= (K-3); i++) K1=K1*2;					
var p1= -1;					
var i2=K;					
while (p1 < K1) {					
	SOCHET(K, P, p1, i2);				
	// печать сочетания				
	for(var i = 1; i <= K; i++) print(P(i));				
}					
					
процедура SOCHET(K, P, p1, i2)  {					
	var i1;  				
	P[i2] = 0;				
	if (i2 < K) go to D1;				
	p1 = p1 + 1;				
	i1=0;				
	if (p1 > 0) {				
		i1=1;			
	D:				
		P[i1]=P[i1]+1;			
		if (P[i1] == 2) {			
			P[i1] = 0;		
			i1=i1+1;		
			go to D;		
		}			
	}				
	i2 = i1;				
D1:					
	i2=i2+1;				
	P[i2]=1;				
					
 // получаем сочетание P[K]					
}
...
Рейтинг: 0 / 0
29.09.2018, 09:44
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39710230
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Поторопился.

Конечно, не процедура, а function.
...
Рейтинг: 0 / 0
29.09.2018, 09:47
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39710232
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Gennadiy Usov,

Зачем тебе goto D1 ?
...
Рейтинг: 0 / 0
29.09.2018, 09:56
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39710238
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Gennadiy UsovА здесь сочетания для К=4
Код: javascript
1.
2.
3.
4.
5.
6.
7.
0	0	0	1
0 	0 	1	0 
0 	1	0 	0 
1	0 	0 	0 
0 	0 	1	1
0 	1	0 	1
1	0  	0 	1

Кстати, последнее сообщение показывает: если набирать операторы в таблице EXCEL в разных колонках, то табуляция сама получится.
Все равно не понимаю логики. По какому принципу выбраны только эти?
Почему нет 0111 ?
...
Рейтинг: 0 / 0
29.09.2018, 10:55
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39710272
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Dima TGennadiy UsovА здесь сочетания для К=4
Код: javascript
1.
2.
3.
4.
5.
6.
7.
0	0	0	1
0 	0 	1	0 
0 	1	0 	0 
1	0 	0 	0 
0 	0 	1	1
0 	1	0 	1
1	0  	0 	1

Кстати, последнее сообщение показывает: если набирать операторы в таблице EXCEL в разных колонках, то табуляция сама получится.Все равно не понимаю логики. По какому принципу выбраны только эти?
Почему нет 0111 ?По условиям задачи пара сочетаний те, которые в сумме составляют сочетание 1111 (для К=4). А у нас уже есть для 0111 пара 1000(№ 4).

Поэтому выбирается одно сочетание из пары, т.е. 1000.
...
Рейтинг: 0 / 0
29.09.2018, 13:16
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39710277
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
maytonGennadiy Usov,
Зачем тебе goto D1 ?В процедуре ищутся две части сочетаний: левая и правая.
р1 отвечает за левую часть, а i2 отвечает за правую часть.
Массив Р - это шаблон сочетаний. D1 нужно для того, чтобы "проскочить" часть операций и поменять одну цифру в шаблоне для нового сочетания.

Далее, при К=3,4 или 5 получаются следующие сочетаний:
Код: javascript
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
для К=3				для К=4					для К=5						
1	0	0		1	0	0	0		1	0	0	0	0		
0	1	0		0	1	0	0		0	1	0	0	0		
0	0	1		0	0	1	0		0	0	1	0	0		
				0	0	0	1		0	0	0	1	0		
				1	1	0	0		0	0	0	0	1		
				1	0	1	0		1	1	0	0	0		
				1	0	0	1		1	0	1	0	0		
									1	0	0	1	0		
									1	0	0	0	1		
									0	1	1	0	0		
									0	1	0	1	0		
									0	1	0	0	1		
									1	1	1	0	0		
									1	1	0	1	0		
									1	1	0	0	1
...
Рейтинг: 0 / 0
29.09.2018, 13:28
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39710309
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Gennadiy Usov,

Да я не это имел в виду. Его можно заменить на if.

Второй goto скорее всего тоже.
...
Рейтинг: 0 / 0
29.09.2018, 15:45
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39710313
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
maytonGennadiy Usov,
Да я не это имел в виду. Его можно заменить на if.
Второй goto скорее всего тоже.По-моему, у этих операторов разные функции.

if - либо то, либо другое.
goto - и то и другое, а в зависимости от обстоятельств, только другое.
...
Рейтинг: 0 / 0
29.09.2018, 16:02
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39710330
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Gennadiy UsovmaytonGennadiy Usov,
Да я не это имел в виду. Его можно заменить на if.
Второй goto скорее всего тоже.По-моему, у этих операторов разные функции.

if - либо то, либо другое.
goto - и то и другое, а в зависимости от обстоятельств, только другое.
Тоесть ты не видишь возможности сделать замену?
...
Рейтинг: 0 / 0
29.09.2018, 17:06
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39710334
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
maytonGennadiy UsovПо-моему, у этих операторов разные функции.
if - либо то, либо другое.
goto - и то и другое, а в зависимости от обстоятельств, только другое.Тоесть ты не видишь возможности сделать замену?Пока нет.
...
Рейтинг: 0 / 0
29.09.2018, 17:13
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39710339
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Gennadiy UsovDima Tпропущено...
Все равно не понимаю логики. По какому принципу выбраны только эти?
Почему нет 0111 ?По условиям задачи пара сочетаний те, которые в сумме составляют сочетание 1111 (для К=4). А у нас уже есть для 0111 пара 1000(№ 4).

Поэтому выбирается одно сочетание из пары, т.е. 1000.
Ясно, тогда лишние 1000 и 1001, меняем их на 0111 и 0110.
В итоге получаем
ДвоичноеДесятичное00011001020011301004010150110601117
Программно цикл такой
Код: plaintext
1.
2.
var max = 2^(K-1);
for(var i = 1; i < max; i++) {вывод i в двоичном виде}


или такой
Код: plaintext
1.
for(var i = (2^(K-1))-1; i > 0; i--) {вывод i в двоичном виде}



PS на это я и намекал 21688530
...
Рейтинг: 0 / 0
29.09.2018, 17:36
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39710346
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Dima T,
Согласен, это есть другое решение задачи.

Если сравнивать эти два варианта решения задачи, то получаем:
1)- в Вашем варианте 3 сочетания по 1, 3 сочетания по 2, 1 сочетание по 3. Всего 12.
- в моём варианте 3 сочетания по 1, 4 сочетания по 2. Всего 11.
Следовательно, в дальнейшем применении процедуры надо будет обрабатывать на 1 объект больше. А это время.

2) - в Вашем варианте идет поиск max = 2^(K-1) чисел
- в моём варианте идет поиск max = 2^(K-3) чисел, а чтобы получить из этих чисел числа max = 2^(K-1) надо будет изменить только один 0 на 1 в массиве Р.

То есть, мой вариант более трудоёмкий по написанию программы, но, наверное, более быстрый(?). Трудно сравнивать битовое представление (а потом развертка на отдельные 0 и 1) и обычное представление.

Кроме того, массив Р может быть намного длиннее, чем i в двоичном виде.
...
Рейтинг: 0 / 0
29.09.2018, 18:23
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39710369
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Gennadiy UsovDima T,
Согласен, это есть другое решение задачи.

Если сравнивать эти два варианта решения задачи, то получаем:
1)- в Вашем варианте 3 сочетания по 1, 3 сочетания по 2, 1 сочетание по 3. Всего 12.
- в моём варианте 3 сочетания по 1, 4 сочетания по 2. Всего 11.
Следовательно, в дальнейшем применении процедуры надо будет обрабатывать на 1 объект больше. А это время.
Твой сложный цикл это тоже лишнее время.

Gennadiy Usov2) - в Вашем варианте идет поиск max = 2^(K-1) чисел
- в моём варианте идет поиск max = 2^(K-3) чисел, а чтобы получить из этих чисел числа max = 2^(K-1) надо будет изменить только один 0 на 1 в массиве Р.
Это за пределами постановки задачи. Выше было сказано что 1000 и 0111 равнозначны и можно взять любое из двух, а сейчас выясняется что одна единица лучше чем три. На сколько лучше?

Откуда появилось max = 2^(K-3) ?
Gennadiy UsovТрудно сравнивать битовое представление (а потом развертка на отдельные 0 и 1) и обычное представление.
Открою тайну: все целые числа хранятся в двоичном виде. Компьютер так устроен что знает только нули и единицы. Десятичные цифры десятичны только в исходном коде, чтобы человеку было удобно читать, а во время исполнения программы используются их двоичные представления.

Gennadiy UsovКроме того, массив Р может быть намного длиннее, чем i в двоичном виде.
Почему?
...
Рейтинг: 0 / 0
29.09.2018, 20:06
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39710373
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Gennadiy Usovmaytonпропущено...
Тоесть ты не видишь возможности сделать замену?Пока нет.

Посмотри. Второй goto можно попробовать заменить на цикл.

Код: javascript
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.
// K – количество чисел (объектов).					
var P = new Array(K+1);					
for(var i = 1; i <= K; i++) P[i]=0;					
					
var K1=1;					
for(var i = 1; i <= (K-3); i++) K1=K1*2;					
var p1= -1;					
var i2=K;					
while (p1 < K1) {					
	SOCHET(K, P, p1, i2);				
	// печать сочетания				
	for(var i = 1; i <= K; i++) print(P(i));				
}					
					
процедура SOCHET(K, P, p1, i2)  {					
	var i1;  				
	P[i2] = 0;				
	if (i2 < K) {				
	   p1 = p1 + 1;				
	   i1=0;				
	   if (p1 <= 0) {				
		   i1=1;			
	   D:				
		   P[i1]=P[i1]+1;			
		   if (P[i1] == 2) {			
			   P[i1] = 0;		
			   i1=i1+1;		
			   go to D;		
		   }			
	   }
	   i2 = i1;				
        }				
	i2=i2+1;				
	P[i2]=1;				
					
 // получаем сочетание P[K]					
}
...
Рейтинг: 0 / 0
29.09.2018, 20:28
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39710445
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
maytonПосмотри. Второй goto можно попробовать заменить на цикл.В моём варианте - надо обойти операторы до D1, а в Вашем - эти операторы выполняются.

Тогда уж лучше
Код: javascript
1.
if (i2 == K) {
...
Рейтинг: 0 / 0
30.09.2018, 06:20
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39710446
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Dima TОткуда появилось max = 2^(K-3) ?Из программы (значение К1):
Код: javascript
1.
2.
3.
4.
5.
6.
7.
8.
9.
var K1=1;					
for(var i = 1; i <= (K-3); i++) K1=K1*2;					
var p1= -1;					
var i2=K;					
while (p1 < K1) {					
	SOCHET(K, P, p1, i2);				
	// печать сочетания				
	for(var i = 1; i <= K; i++) print(P(i));				
}

Ещё раз посмотрите на картинку 21689842 : справа в сочетаниях всегда для одного значения слева формируется "лесенка" с убыванием от размера К до размера 3
Код: javascript
1.
2.
3.
4.
					
1	0	0		
0	1	0		
0	0	1
...
Рейтинг: 0 / 0
30.09.2018, 06:29
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39710448
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Dima TGennadiy UsovКроме того, массив Р может быть намного длиннее, чем i в двоичном виде.Почему?Здесь необходимо уточнение (или сравнение), так как пока путаюсь:
- какое максимальное целое число в битах можно представить в компьютере;
- какой максимальный размер массива Р можно представить в компьютере?

Хочется сравнить эти числа, так как в дальнейшем идет разговор о больших досках (соседний топик).
...
Рейтинг: 0 / 0
30.09.2018, 06:35
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39710449
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
И ещё один момент:Dima TПрограммно цикл такой
Код: plaintext
1.
for(var i = (2^(K-1))-1; i > 0; i--) {вывод i в двоичном виде}

Мне нужно не двоичное представление, а отдельные цифры из этого двоичного представления, т.е. массив цифр 0 и 1.

Выборка таких цифр из числа, кажется, с помощью деления на 2. У меня только сложение. Пока не знаю, что быстрее.
...
Рейтинг: 0 / 0
30.09.2018, 07:36
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39710526
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Gennadiy Usovсправа в сочетаниях всегда для одного значения слева формируется "лесенка" с убыванием от размера К до размера 3
Как понимаю "лесенка" - это вхождение в размер К всех размеров менее К.

Если так, то в любой системе счисления есть "лесенка", т.к. они все позиционные .
...
Рейтинг: 0 / 0
30.09.2018, 14:23
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39710528
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Gennadiy UsovDima Tпропущено...
Почему?Здесь необходимо уточнение (или сравнение), так как пока путаюсь:
- какое максимальное целое число в битах можно представить в компьютере;
- какой максимальный размер массива Р можно представить в компьютере?

Хочется сравнить эти числа, так как в дальнейшем идет разговор о больших досках (соседний топик).
Любое число. Процессор оперирует 32 и 64 битными словами, но никто не мешает взять массив слов и логически рассматривать его как одно число. Операции сравнения (больше, меньше, равно) сделать элементарно для этого числа.
Максимальный размер массива зависит от количества имеющейся памяти и размера элемента массива. Для простоты считай что возможен массив из 100 млн. элементов.

В принципе без разницы как представлено число: массив слов (двоичное представление) или просто массив где один элемент один бит. Второй способ просто займет больше памяти и медленнее будет обратываться.
...
Рейтинг: 0 / 0
30.09.2018, 14:36
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39710529
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Dima TGennadiy Usovсправа в сочетаниях всегда для одного значения слева формируется "лесенка" с убыванием от размера К до размера 3Как понимаю "лесенка" - это вхождение в размер К всех размеров менее К.
Если так, то в любой системе счисления есть "лесенка", т.к. они все позиционные .Не совсем так.

В сообщении 21689842 хорошо видны эти "лесенки".
Если идти сверху картинки К=5, то видно, что:
- сначала "лесенка" 5х5 - 5 сочетаний
- далее для 1 "лесенка" 4х4 - 4 сочетания
- далее для 01 "лесенка" 3х3 - 3 сочетания
- далее для 11 "лесенка" 3х3 - 3 сочетания. Итого 15 сочетаний.
А слева в каждом из этих сочетаний сформированы числа от 00 до 11.(К-3 = 2)
...
Рейтинг: 0 / 0
30.09.2018, 14:40
| Ответить | Цитировать | Написать  
Поиск любых сочетаний из К чисел
    #39710532
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Gennadiy UsovИ ещё один момент:Dima TПрограммно цикл такой
Код: plaintext
1.
for(var i = (2^(K-1))-1; i > 0; i--) {вывод i в двоичном виде}

Мне нужно не двоичное представление, а отдельные цифры из этого двоичного представления, т.е. массив цифр 0 и 1.

Выборка таких цифр из числа, кажется, с помощью деления на 2. У меня только сложение. Пока не знаю, что быстрее.
Деление на 2 не требует деления в двоичной системе. Это сдвиг. Ты же не делишь на 10 в десятичной, а просто сдвигаешь запятую.

Схематично вывод делается так
Код: javascript
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
function print_bit(value) {
  mask = 1 << K;
  while(mask != 0) {
     if((value & mask) == 0) {
         print("0");
     } else {
         print("1");
     }
     mask = mask >> 1;
}



Думаю тебе будет интересно почитать что такое битовые операции и булева алгебра . Если по-простому - это набор операций для двоичной системы счисления.
...
Рейтинг: 0 / 0
30.09.2018, 14:57
| Ответить | Цитировать | Написать  
25 сообщений из 206, страница 4 из 9
  4  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Поиск любых сочетаний из К чисел
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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