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

Откуда:
Сообщений: 1531
Dima T
Схематично вывод делается так
function print_bit(value) {
  mask = 1 << K;
  while(mask != 0) {
     if((value & mask) == 0) {
         print("0");
     } else {
         print("1");
     }
     mask = mask >> 1;
}
Тогда можно будет определить все сочетания для К объектов.Так?
// K – количество чисел (объектов).				
var P = new Array(K+1);				
// количество сочетаний				
var K1=1;				
for(var i = 1; i <=K; i++) K1=K1*2;				
K1=K1-1;				
// поиск всех сочетаний для К объектов				
for(var i = 0; i <= K1; i++) {				
	for(var i = 1; i <= K; i++) P[i]=0;			
	sochet_new(i);			
}				
				
				
function sochet_new(i) {				
	var i1=0;			
	mask = 1 << i;			
	while(mask != 0) {			
		i1=i1+1;		
		P[i1]=value & mask;		
	}			
	mask = mask >> 1;			
}				
Есть одно сомнение: для число 1 в массиве Р "1" находится в начале массива или в конце?
5 окт 18, 19:47    [21696770]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1531
Что-то я намудрил в предыдущем сообщении. Теперь кажется верно:
// K – количество чисел (объектов).					
var P = new Array(K+1);					
// количество сочетаний					
var K1=1;					
for(var k = 1; k <=K; k++) K1=K1*2;					
K1=K1-1;					
var dlina1=1;					
var dlina2=1;					
// поиск всех сочетаний для К объектов					
for(var k1 = 0; k1 <= K1; k1++) {					
	for(var k = 1; k <= K; k++) P[k]=0;				
	if (k1>dlina1) {				
		dlina1=dlina1*2;			
		dlina2=dlina2+1;			
	}				
	sochet_new(k1, dlina2);
	// печать сочетания P[K]			
}					
					
					
function sochet_new(value, dlina2) {					
	var i1=0;				
	mask = 1 << dlina2;				
	while(mask != 0) {				
		i1=i1+1;			
		P[i1]=value & mask;			
	}				
	mask = mask >> 1;				
}
6 окт 18, 13:40    [21696995]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13717
Gennadiy Usov
Что-то я намудрил в предыдущем сообщении. Теперь кажется верно:

Тут тоже намудрил, это надо внутрь цикла, иначе он будет бесконечный
	mask = mask >> 1;				


И это под вопросом:
		P[i1]=value & mask;			

value & mask дает или 0, или mask, выше ты 0 и 1 использовал, не знаю важно ли это для твоей задачи.
7 окт 18, 16:33    [21697391]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1531
Dima T
Тут тоже намудрил, это надо внутрь цикла, иначе он будет бесконечный
	mask = mask >> 1;	
И это под вопросом:
		P[i1]=value & mask;	
value & mask дает или 0, или mask, выше ты 0 и 1 использовал, не знаю важно ли это для твоей задачи.
Спасибо! Понял. Теперь так?
function sochet_new(value, dlina2) {					
	var i1=0;				
	mask = 1 << dlina2;				
	while(mask != 0) {				
		i1=i1+1;			
		if((value & mask) == 0) {			
			P[i1]=0;		
		} else {			
			P[i1]=1;		
		}			
		mask = mask >> 1;			
	}				
}
7 окт 18, 16:55    [21697400]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1531
В сообщениях 21696995 и 21697400представлена программа по поиску всех сочетаний К чисел.
Однако, если величина К окажется слишком большой, например, 200, 250, то в программе появляются большие числа: 2^200, 2^250, что приводит к необходимости вводить дополнительные программы для работы с такими большими числами.

В сообщениях 21697951 и 21698205 высказана мысль о переходе в программах, где есть большие числа, на другие числа, например, на величину степени 2 таких чисел.

Однако выше указанная программа, которая основывается на программе21690391, предполагает разложение чисел вида 2^200 на отдельные биты, что не позволяет избавиться от больших чисел.

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

Откуда:
Сообщений: 1531
А в этой программе не требуется использовать большие числа:
// K – количество чисел (объектов).				
var P = new Array(K+2);				
for(var i = 1; i <= K+1; i++) P[i]=0;				
				
while (P[К+1]< 1) {				
	SOCHET3(K, P);			
	// печать сочетания			
	for(var i = 1; i <= K; i++) print(P[i]);			
}				
				
function SOCHET3(K, P)  {				
	var i1;  			
	i1=1;			
D:				
	P[i1]=P[i1]+1;			
	if (P[i1] == 2) {			
		P[i1] = 0;		
		i1=i1+1;		
		go to D;		
	}			
 // получаем сочетание P[K]				
} 
Так что, получаем все сочетания. Где-то помогла картинка 21281836
8 окт 18, 20:42    [21698634]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

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

Так и не смог избавится от go to?
8 окт 18, 20:48    [21698636]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

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

Так и не смог избавится от go to?

mayton, он только учится программировать, пока хоть так, потом почитает правила хорошего тона.
8 окт 18, 21:03    [21698644]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

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

Так и не смог избавится от go to?
Пока не вижу альтернативы
8 окт 18, 21:10    [21698649]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

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

Так и не смог избавится от go to?
Пока не вижу альтернативы

Альтернатива это цикл и break
function SOCHET3(K, P)  {				
	var i1;  			
	i1=1;			
	while(true) {
		P[i1]=P[i1]+1;			
		if (P[i1] != 2) break; // Выход из цикла если P[i1] != 2
		P[i1] = 0;		
		i1=i1+1;		
	}
}

Но в этом коде есть ошибка: i1 может выйти за пределы размера массива P[], поэтому лучше так
function SOCHET3(K, P)  {				
	for(var i1 = 1; i1 <=K; i1++) {
		P[i1]=P[i1]+1;			
		if (P[i1] != 2) break; // Выход из цикла если P[i1] != 2
		P[i1] = 0;		
	}
}
9 окт 18, 07:54    [21698841]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1531
Спасибо за 2 варианта программ!
Dima T
Но в этом коде есть ошибка: i1 может выйти за пределы размера массива P[], поэтому лучше так
function SOCHET3(K, P)  {				
	for(var i1 = 1; i1 <=K; i1++) {
		P[i1]=P[i1]+1;			
		if (P[i1] != 2) break; // Выход из цикла если P[i1] != 2
		P[i1] = 0;		
	}
}
Данный вариант очень интересен с точки зрения упрощения программы.

Однако, все сочетания определяются в некотором цикле от 1 до ..... Процедура SOCHET3 будет в этом цикле.
Последним сочетанием должно быть 1111111111 и т.д. А цикл будет работать дальше.

Поэтому необходимо ввести ячейку P[К+1]. И пусть i1 выходит за пределы размера массива P[К], где мы 1 отловим в ячейке P[К+1].

Поэтому мне очень понравился 1-ый вариант. Никогда не работал со значениями true, поэтому спасибо за учение. Кстати, true можно применить и в оболочке над SOCHET3
			
// K – количество чисел (объектов).			
var P = new Array(K+2);			
for(var i = 1; i <= K+1; i++) P[i]=0;			
			
while(true) {			
	SOCHET3(K, P);		
	if (P[К+1]==1) break; // Выход из цикла по сочетаниям		
	// применение сочетаний
        // печать сочетания		
	for(var i = 1; i <= K; i++) print(P[i]);		
}			
			
function SOCHET3(K, P)  {			
	var i1;  		
	i1=1;		
	while(true) {		
		P[i1]=P[i1]+1;	
		if (P[i1] != 2) break; // Выход из цикла если P[i1] != 2	
		P[i1] = 0;	
		i1=i1+1;	
	}		
}
9 окт 18, 15:00    [21699362]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13717
Gennadiy Usov
Однако, все сочетания определяются в некотором цикле от 1 до ..... Процедура SOCHET3 будет в этом цикле.
Последним сочетанием должно быть 1111111111 и т.д. А цикл будет работать дальше.

Поэтому необходимо ввести ячейку P[К+1]. И пусть i1 выходит за пределы размера массива P[К], где мы 1 отловим в ячейке P[К+1]

Вот мы уже плавно подошли к теме обработки ошибок. Отлавливать ошибку в P[К+1] не самый красивый способ.
Лучше выбрать какое-то правило для обработки ошибок и его использовать. Например функция возвращает true в случае успешного выполнения.
В этом случае можно так
function SOCHET3(K, P)  {				
	var i1;
	for(i1 = 1; i1 <=K; i1++) {
		P[i1]=P[i1]+1;			
		if (P[i1] != 2) break; // Выход из цикла если P[i1] != 2
		P[i1] = 0;		
	}
        return i1 <= K;
}


тогда вывод можно будет переписать так
while(SOCHET3(K, P)) {			
        // печать сочетания		
	for(var i = 1; i <= K; i++) print(P[i]);		
}			


PS Советую сделать паузу и прочитать какую-нибудь книгу по основам программирования.
9 окт 18, 15:22    [21699386]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1531
Dima T
Например функция возвращает true в случае успешного выполнения.
В этом случае можно так
function SOCHET3(K, P)  {				
	var i1;
	for(i1 = 1; i1 <=K; i1++) {
		P[i1]=P[i1]+1;			
		if (P[i1] != 2) break; // Выход из цикла если P[i1] != 2
		P[i1] = 0;		
	}
        return i1 <= K;
}
тогда вывод можно будет переписать так
while(SOCHET3(K, P)) {			
        // печать сочетания		
	for(var i = 1; i <= K; i++) print(P[i]);		
}			

PS Советую сделать паузу и прочитать какую-нибудь книгу по основам программирования.
Пока некогда делать паузу.

Надо подвести некоторую черту.
Что мы имеем:
- вариант программы определения сочетаний для большого числа К21699386 (на основании картинок21281836);
- вариант программы определения сочетаний для небольшого числа К2169677021697400 с использованием идеи21690391.

Кому что нравится.
9 окт 18, 15:54    [21699436]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 41068
Что от нас требуется?
9 окт 18, 18:32    [21699600]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1531
mayton
Что от нас требуется?
Да ничего
9 окт 18, 19:33    [21699668]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1531
Gennadiy Usov
Надо подвести некоторую черту.
Что мы имеем:
- вариант программы определения сочетаний для большого числа К21699386 (на основании картинок21281836);
- вариант программы определения сочетаний для небольшого числа К2169677021697400 с использованием идеи21690391.
В первом варианте, как правило, перебираются "1" только в части двоичного вида числа, определяющего сочетание.

Во втором варианте маски перебирают все элементы двоичного вида числа, определяющего сочетание.

В первом варианте можно значительно уменьшить количество переборов, если массив P[K] разделим на несколько частей, и "работаем" отдельно с каждой частью.

Например, число К делится на 3. Тогда получаем программу (используем вариант21699436, предложенный Dima T):
// K – количество чисел (объектов).					
var P = new Array(K+1);					
for(var i = 1; i <= K; i++) P[i]=0;					
					
var K1=K/3;					
P[1] = -1;
P[K1+1] = -1;					
P[2*K1+1] = -1;					
					
var K2=0;					
var K3=2*K1;					
while(SOCHET4(K1, P, K2)) {					
	while(SOCHET4(K1, P, K3)) {				
		while(SOCHET4(K1, P, K1)) {			
			
			// печать сочетания		
			for(var i = 1; i <= K; i++) print(P[i]);		
			}		
		}			
	}				
}					
					
function SOCHET4(K1, P, i2)  {					
	var i1;				
	for(i1 = i2+1; i1 <=i2+K1; i1++) {				
		P[i1]=P[i1]+1;			
		if (P[i1] != 2) break; // Выход из цикла если P[i1] != 2			
		P[i1] = 0;			
	}				
	return i1 <= i2+K1;				
}					
12 окт 18, 19:37    [21702893]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1531
В предыдущем сообщении массив P[K] был разделе на 3 равные части , и в каждой его части искались свои сочетания, а потом все эти сочетания совмещались в одно сочетание.

Оказывается, такое разделение (произвольное) можно сделать для любого массива P[K]. Таким образом, можно уйти от больших чисел.

Например, надо найти сочетания для 100 чисел.

Делим массив P[100] на 4 части, например, 15, 35, 27, 23. Тогда, используя результаты сообщения 21702893, получаем программу поиска сочетаний для 100 чисел:
var K=100;							
var P = new Array(K+1);							
for(var i = 1; i <= K; i++) P[i]=0;							
							
var K1=15;							
var K2=35;							
var K3=27;							
var K4=23;							
var Q1=0;							
var Q2= 15;							
var Q3=50;							
var Q4=77;							
P[1] = -1;							
P[15+1] = -1;							
P[50+1] = -1;							
P[77+1] = -1;							
							
while(SOCHET4(K1, P, Q1)) {							
	while(SOCHET4(K2, P, Q2)) {						
		while(SOCHET4(K3, P, Q3)) {					
			while(SOCHET4(K4, P, Q4)) {				
				// печать сочетания			
				for(var i = 1; i <= K; i++) print(P[i]);			
				}			
			}				
		}					
	}						
}	
Правда, первое сочетание будет состоять из одних 0, но пока от этого не удаётся избавиться.
13 окт 18, 12:54    [21703238]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1531
В двух последних сообщениях 21702893 и 21703238 лишняя закрывающая скобка } в головной программе.
13 окт 18, 17:51    [21703339]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 41068
Этот кусок кода имеет рекурсивную природу. Убежден что его можно переписать на более компактный вид.

while(SOCHET4(K1, P, Q1)) {							
	while(SOCHET4(K2, P, Q2)) {						
		while(SOCHET4(K3, P, Q3)) {					
			while(SOCHET4(K4, P, Q4)) {				
				// печать сочетания			
				for(var i = 1; i <= K; i++) print(P[i]);			
				}			
			}				
		}					
	}						
}	
13 окт 18, 17:54    [21703341]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1531
mayton
Этот кусок кода имеет рекурсивную природу. Убежден что его можно переписать на более компактный вид.
Возможно.

Однако, не всегда в таких программах будет одна и та же процедура.
Весь смысл такой разбивки не только в том, чтобы уйти от больших чисел.

Могут быть процедуры, которые будут решать специальные задачи на отдельных участках массива P[K]. Например, сравнение с другими участками.
13 окт 18, 18:56    [21703362]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1531
А теперь можно вернуться к одной из задач по специальным сочетаниям:21283022
«Имеется несколько последовательностей чисел: 1,2,3, далее 1,2,3,4,5,6, далее 1,2,3,4,5,6,7,8,9, и т.д.
Для каждой нужно найти все сочетания. При этом:
В первой последовательности в одном сочетании не могут быть 1 и 2, 2 и 3, во второй - 1 и 3, 2 и 4, 3 и 5, 4 и 6, в третьей - 1 и 4, 2 и 5, 3 и 6, 4 и 7, 5 и 8, 6 и 9 и т.д.
Здесь видно, что существует некоторая прогрессия, которую можно распространить на последовательность, длиной 3 х К.
Вот и все.»

Можно взять программу 21702893 и добавить к ней процедуру SOCHET5, которая сравнивает значения «1» в 3-х разделах массива P[K].
// K – количество чисел (объектов).						
var P = new Array(K+1);						
for(var i = 1; i <= K; i++) P[i]=0;						
						
var K1=K/3;						
P[K1+1] = -1;						
P[2*K1+1] = -1;						
P[1] = -1;						
						
var K2=0;						
var K3=2*K1						
while(SOCHET4(K1, P, K2)) {						
	while(SOCHET4(K1, P, K3)) {					
		while(SOCHET5(K1, P, K1)) {				
			// печать сочетания			
			for(var i = 1; i <= K; i++) print(P[i]);			
		}				
	}					
}						
						
function SOCHET5(K1, P, i2)  {						
	var i1;					
	for(i1 = i2+1; i1 <=i2+K1; i1++) {					
		P[i1]=P[i1]+1;				
		if(P[i1] == 1)  {				
			if((P[i1 - K1] == 1) || (P[i1 + K1] == 1)) {			
				P[i1]=2;		
				for(var i = i2+1; i <= i1-1; i++) P[i]=0;		
			}			
		}				
		if (P[i1] != 2) break; // Выход из цикла если P[i1] != 2				
		P[i1] = 0;				
	}					
	return i1 <= i2+K1;					
}						
14 окт 18, 06:50    [21703514]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 41068
Обычно цикл WHILE имеет обязывает программиста реализовать следующий паттерн:

<инициализация>
while(<условие цикла>) {
   <тело цикла>
   <итерационное выражение>
}


Если вы опускаете итерационное выражение то рискуете получить бесконечный цикл. Теоретически
это выражение может быть инкапсулировано в функцию условия но в вашем случае - есть сомнения
что это реализовано.
14 окт 18, 16:24    [21703650]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
Dima T
Member

Откуда:
Сообщений: 13717
mayton, 21699386
14 окт 18, 17:01    [21703659]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 41068
Dima T, вы тестировали это?
14 окт 18, 17:04    [21703660]     Ответить | Цитировать Сообщить модератору
 Re: Поиск любых сочетаний из К чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 41068
Может оно и работает. ХЗ. Но эти функции с глобальным состоянием. Это ... unsupportable. Зачем так вообще делать?
14 окт 18, 17:25    [21703665]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 4 5 [6] 7 8 9   вперед  Ctrl      все
Все форумы / Программирование Ответить