Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 [4] 5 6 7 8 9   вперед  Ctrl      все
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1449
mayton
Gennadiy Usov,
JavaScript не умеет возводить в степень так как вы описали.
С одной стороны похвально что вы пытаетесь помочь. С другой стороны это выглядит как медвежья услуга.
И помогли и запутали.
Тогда по другому:
var K1=1;
for(var i = 1; i <= (K-3); i++) K1=K1*2;
К1=К1-1;
28 сен 18, 15:14    [21689174]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1449
Dima T
Gennadiy Usov
При К = 3 должно получиться 100, 010, 001.
А при К = 4 добавится 1000, 0100, 0010, 0001. Так ?
Если так то это К вариантов, а не 2^(K-1)
И показанное это степени двойки, если рассматривать эти числа как двоичные, т.е.
2^0 = 0b0001 = 1
2^1 = 0b0010 = 2
2^2 = 0b0100 = 4
2^3 = 0b1000 = 8
А здесь сочетания для К=4
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
28 сен 18, 18:09    [21689414]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1449
Gennadiy Usov
[/src]
А здесь сочетания для К=4
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 в разных колонках, то табуляция сама получится.
29 сен 18, 06:04    [21689720]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1449
Это текст, подготовленный в таблице EXCEL.

Постарался большую часть определения сочетаний "запрятать" в процедуру.
// 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]					
} 
29 сен 18, 09:44    [21689747]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1449
Поторопился.

Конечно, не процедура, а function.
29 сен 18, 09:47    [21689748]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 39873
Gennadiy Usov,

Зачем тебе goto D1 ?
29 сен 18, 09:56    [21689753]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13553
Gennadiy Usov
А здесь сочетания для К=4
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 ?
29 сен 18, 10:55    [21689765]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1449
Dima T
Gennadiy Usov
А здесь сочетания для К=4
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.
29 сен 18, 13:16    [21689836]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1449
mayton
Gennadiy Usov,
Зачем тебе goto D1 ?
В процедуре ищутся две части сочетаний: левая и правая.
р1 отвечает за левую часть, а i2 отвечает за правую часть.
Массив Р - это шаблон сочетаний. D1 нужно для того, чтобы "проскочить" часть операций и поменять одну цифру в шаблоне для нового сочетания.

Далее, при К=3,4 или 5 получаются следующие сочетаний:
для К=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	
29 сен 18, 13:28    [21689842]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 39873
Gennadiy Usov,

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

Второй goto скорее всего тоже.
29 сен 18, 15:45    [21689888]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1449
mayton
Gennadiy Usov,
Да я не это имел в виду. Его можно заменить на if.
Второй goto скорее всего тоже.
По-моему, у этих операторов разные функции.

if - либо то, либо другое.
goto - и то и другое, а в зависимости от обстоятельств, только другое.
29 сен 18, 16:02    [21689894]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 39873
Gennadiy Usov
mayton
Gennadiy Usov,
Да я не это имел в виду. Его можно заменить на if.
Второй goto скорее всего тоже.
По-моему, у этих операторов разные функции.

if - либо то, либо другое.
goto - и то и другое, а в зависимости от обстоятельств, только другое.

Тоесть ты не видишь возможности сделать замену?
29 сен 18, 17:06    [21689914]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1449
mayton
Gennadiy Usov
По-моему, у этих операторов разные функции.
if - либо то, либо другое.
goto - и то и другое, а в зависимости от обстоятельств, только другое.
Тоесть ты не видишь возможности сделать замену?
Пока нет.
29 сен 18, 17:13    [21689918]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

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

Поэтому выбирается одно сочетание из пары, т.е. 1000.

Ясно, тогда лишние 1000 и 1001, меняем их на 0111 и 0110.
В итоге получаем
ДвоичноеДесятичное
00011
00102
00113
01004
01015
01106
01117

Программно цикл такой
var max = 2^(K-1);
for(var i = 1; i < max; i++) {вывод i в двоичном виде}

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


PS на это я и намекал 21688530
29 сен 18, 17:36    [21689923]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1449
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 в двоичном виде.
29 сен 18, 18:23    [21689938]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13553
Gennadiy Usov
Dima T,
Согласен, это есть другое решение задачи.

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

Твой сложный цикл это тоже лишнее время.

Gennadiy Usov
2) - в Вашем варианте идет поиск 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 в двоичном виде.

Почему?
29 сен 18, 20:06    [21690037]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 39873
Gennadiy Usov
mayton
пропущено...
Тоесть ты не видишь возможности сделать замену?
Пока нет.


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

// 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]					
} 
29 сен 18, 20:28    [21690051]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1449
mayton
Посмотри. Второй goto можно попробовать заменить на цикл.
В моём варианте - надо обойти операторы до D1, а в Вашем - эти операторы выполняются.

Тогда уж лучше
if (i2 == K) {
30 сен 18, 06:20    [21690212]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1449
Dima T
Откуда появилось max = 2^(K-3) ?
Из программы (значение К1):
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
					
1	0	0		
0	1	0		
0	0	1	
30 сен 18, 06:29    [21690213]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1449
Dima T
Gennadiy Usov
Кроме того, массив Р может быть намного длиннее, чем i в двоичном виде.
Почему?
Здесь необходимо уточнение (или сравнение), так как пока путаюсь:
- какое максимальное целое число в битах можно представить в компьютере;
- какой максимальный размер массива Р можно представить в компьютере?

Хочется сравнить эти числа, так как в дальнейшем идет разговор о больших досках (соседний топик).
30 сен 18, 06:35    [21690215]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1449
И ещё один момент:
Dima T
Программно цикл такой
for(var i = (2^(K-1))-1; i > 0; i--) {вывод i в двоичном виде}
Мне нужно не двоичное представление, а отдельные цифры из этого двоичного представления, т.е. массив цифр 0 и 1.

Выборка таких цифр из числа, кажется, с помощью деления на 2. У меня только сложение. Пока не знаю, что быстрее.
30 сен 18, 07:36    [21690216]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13553
Gennadiy Usov
справа в сочетаниях всегда для одного значения слева формируется "лесенка" с убыванием от размера К до размера 3

Как понимаю "лесенка" - это вхождение в размер К всех размеров менее К.

Если так, то в любой системе счисления есть "лесенка", т.к. они все позиционные.
30 сен 18, 14:23    [21690381]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13553
Gennadiy Usov
Dima T
пропущено...
Почему?
Здесь необходимо уточнение (или сравнение), так как пока путаюсь:
- какое максимальное целое число в битах можно представить в компьютере;
- какой максимальный размер массива Р можно представить в компьютере?

Хочется сравнить эти числа, так как в дальнейшем идет разговор о больших досках (соседний топик).

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

В принципе без разницы как представлено число: массив слов (двоичное представление) или просто массив где один элемент один бит. Второй способ просто займет больше памяти и медленнее будет обратываться.
30 сен 18, 14:36    [21690385]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1449
Dima T
Gennadiy Usov
справа в сочетаниях всегда для одного значения слева формируется "лесенка" с убыванием от размера К до размера 3
Как понимаю "лесенка" - это вхождение в размер К всех размеров менее К.
Если так, то в любой системе счисления есть "лесенка", т.к. они все позиционные.
Не совсем так.

В сообщении21689842хорошо видны эти "лесенки".
Если идти сверху картинки К=5, то видно, что:
- сначала "лесенка" 5х5 - 5 сочетаний
- далее для 1 "лесенка" 4х4 - 4 сочетания
- далее для 01 "лесенка" 3х3 - 3 сочетания
- далее для 11 "лесенка" 3х3 - 3 сочетания. Итого 15 сочетаний.
А слева в каждом из этих сочетаний сформированы числа от 00 до 11.(К-3 = 2)
30 сен 18, 14:40    [21690386]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13553
Gennadiy Usov
И ещё один момент:
Dima T
Программно цикл такой
for(var i = (2^(K-1))-1; i > 0; i--) {вывод i в двоичном виде}
Мне нужно не двоичное представление, а отдельные цифры из этого двоичного представления, т.е. массив цифр 0 и 1.

Выборка таких цифр из числа, кажется, с помощью деления на 2. У меня только сложение. Пока не знаю, что быстрее.

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

Схематично вывод делается так
function print_bit(value) {
  mask = 1 << K;
  while(mask != 0) {
     if((value & mask) == 0) {
         print("0");
     } else {
         print("1");
     }
     mask = mask >> 1;
}


Думаю тебе будет интересно почитать что такое битовые операции и булева алгебра. Если по-простому - это набор операций для двоичной системы счисления.
30 сен 18, 14:57    [21690391]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 [4] 5 6 7 8 9   вперед  Ctrl      все
Все форумы / Программирование Ответить