Программирование, т. 5.1.

Жопой прочел, хуевый день у меня.

бля, чота я не могу придумать нормальный перебор средствами цикла чтоб пробовало поочерёдно все возможные комбинации

хоть бери и рекурсию хуярь

ну я придумал только рекурсивное решение

ну мне в голову нерекурсивного никакого не приодит

но рекурсией это по идее изи

ща подниму исходники старого решателя судоку который работал нерекурсивно и пошагово ебашил пошагово влево-справо, может смогу портировать это решение сюда

чето мне говорит если циклами пробовать то решение будет сложнее O(n^2)

там как раз не циклами, кол-во операций должно быть где~то такое же

я щас сначала рекурсивный вариант закончу чтоб лучше понять что там внутри должно происходить, потом тот попробую

Ты хочешь сказать что у тебя сейчас решение n^2 или даже ниже?

не больше чем n^2 получается, если я не ошибаюсь

Combo: -4, -2, -1, 1, 0,5, 2,5, 6, 7
Combo: -4, -2, -1, 1, 4, 5, 7
Combo: -4, -2, -1, 1, 6, 10
Combo: -4, -2, -1, 1, 5, 11
Combo: -4, -2, -1, 0,5, 2,5, 4, 10
Combo: -4, -2, -1, 4, 6, 7
Combo: -4, -2, -1, 6, 11
Combo: -4, -2, -1, 7, 10
Combo: -4, -2, 1, 0,5, 2,5, 5, 7
Combo: -4, -2, 1, 4, 6, 5
Combo: -4, -2, 1, 4, 11
Combo: -4, -2, 1, 5, 10
Combo: -4, -2, 0,5, 2,5, 6, 7
Combo: -4, -2, 4, 5, 7
Combo: -4, -2, 6, 10
Combo: -4, -2, 5, 11
Combo: -4, -1, 1, 0,5, 2,5, 4, 7
Combo: -4, -1, 1, 0,5, 2,5, 6, 5
Combo: -4, -1, 1, 0,5, 2,5, 11
Combo: -4, -1, 1, 4, 10
Combo: -4, -1, 0,5, 2,5, 5, 7
Combo: -4, -1, 4, 6, 5
Combo: -4, -1, 4, 11
Combo: -4, -1, 5, 10
Combo: -4, 1, 0,5, 2,5, 4, 6
Combo: -4, 1, 0,5, 2,5, 10
Combo: -4, 1, 6, 7
Combo: -4, 0,5, 2,5, 4, 7
Combo: -4, 0,5, 2,5, 6, 5
Combo: -4, 0,5, 2,5, 11
Combo: -4, 4, 10
Combo: -2, -1, 1, 0,5, 2,5, 4, 5
Combo: -2, -1, 1, 5, 7
Combo: -2, -1, 0,5, 2,5, 4, 6
Combo: -2, -1, 0,5, 2,5, 10
Combo: -2, -1, 6, 7
Combo: -2, 1, 4, 7
Combo: -2, 1, 6, 5
Combo: -2, 1, 11
Combo: -2, 0,5, 2,5, 4, 5
Combo: -2, 5, 7
Combo: -1, 1, 0,5, 2,5, 7
Combo: -1, 1, 4, 6
Combo: -1, 1, 10
Combo: -1, 4, 7
Combo: -1, 6, 5
Combo: -1, 11
Combo: 1, 0,5, 2,5, 6
Combo: 1, 4, 5
Combo: 0,5, 2,5, 7
Combo: 4, 6
Combo: 10

там вообще прилично побольше чем n^2, разве нет?

операции-то на каждом вызове, а не только на конечных точках

После того как я проиграл (и понял что там ебанутая сложность) полез гуглить ради науки

http://stackoverflow...ach-a-given-sum

Там чувак с заплюсованным ответом пишет что сложность 2^n, то есть при 10 элементах будет 1024 итерации.

Или я не то нагуглил?

вообще может быть, я точно не уверен

хз, изи решается же

Stack *st=NULL;
for(int i=0;i<length;i++){
 if(a[i]<=10){
  Push(&st,a[i]);
  foo(i,10-a[i],&st);
  while(st!=NULL)
Pop(&st);
 }
}

return 0;
}

void foo(int i, int s, Stack **st){
for(int j=i+1;j<length;j++){
 if(a[j]<=s){
  Push(st,a[j]);
  foo(j,s-a[j],st);
 }
}
if(s==0){
 printf_stack(st);
}
Pop(st);
}

эх, ща бы в яндекс устроиться

хз, изи решается же

Stack *st=NULL;
for(int i=0;i<length;i++){
 if(a[i]<=10){
  Push(&st,a[i]);
  foo(i,10-a[i],&st);
  while(st!=NULL)
Pop(&st);
 }
}

return 0;
}

void foo(int i, int s, Stack **st){
for(int j=i+1;j<length;j++){
 if(a[j]<=s){
  Push(st,a[j]);
  foo(j,s-a[j],st);
 }
}
if(s==0){
 printf_stack(st);
}
Pop(st);
}

       static float[] arr = { -4, -2, -1, 1, 0.5F, 2.5F, 4, 6, 5, 7, 10, 11 };
       static List<int> list = new List<int>();

       static int findNext(int i, float summ)
       {
           summ += arr[i];

           if (summ == 10.0)
           {
               printf(list, i);
           }
           else if (summ < 10.0)
           {
               list.Add(i);

               for (int j = i + 1; j < arr.Length; j++)
                   findNext(j, summ);

               list.Remove(i);
           }
           return 0;
       }


       static void Main(string[] args)
       {
           list.Clear();
           for (int i = 0; i < arr.Length; i++)
           {
               findNext(i, 0);
           }
       }

у меня финальный вариант такой получился

import java.util.HashMap;
import java.util.Map;
import java.util.stream.IntStream;
public class Main {
static final int DESIRED_SUM = 10;
static double[] values = {-4, -2, -1, 0, 0, 1, 0.5, 2.5, 4, 6, 5, 7, 10, 11};
public static void main(String[] args) {
	Map<Integer, Integer> matchedIndexes = new HashMap<>();
	IntStream.range(0, values.length)
			.forEach(x -> IntStream.range(x + 1, values.length)
					.filter(f -> !matchedIndexes.containsValue(f))
					.forEach(y -> {
						if (values[x] + values[y] == DESIRED_SUM)
							matchedIndexes.put(x, y);
						return;
					}));
	matchedIndexes.forEach((x, y) -> System.out.println(values[x] + " " + values[y]));
}
}

-1.0 11.0

0.0 10.0

4.0 6.0

Process finished with exit code 0

http://pastie.org/10021488

import java.util.HashMap;
import java.util.Map;
import java.util.stream.IntStream;
public class Main {
static final int DESIRED_SUM = 10;
static double[] values = {-4, -2, -1, 0, 0, 1, 0.5, 2.5, 4, 6, 5, 7, 10, 11};
public static void main(String[] args) {
	Map<Integer, Integer> matchedIndexes = new HashMap<>();
	IntStream.range(0, values.length)
			.forEach(x -> IntStream.range(x + 1, values.length)
					.filter(f -> !matchedIndexes.containsValue(f))
					.forEach(y -> {
						if (values[x] + values[y] == DESIRED_SUM)
							matchedIndexes.put(x, y);
						return;
					}));
	matchedIndexes.forEach((x, y) -> System.out.println(values[x] + " " + values[y]));
}
}

 

http://pastie.org/10021488

это выглядит как поиск только пар, а не всех комбинаций, нет?

import java.util.HashMap;
import java.util.Map;
import java.util.stream.IntStream;
public class Main {
static final int DESIRED_SUM = 10;
static double[] values = {-4, -2, -1, 0, 0, 1, 0.5, 2.5, 4, 6, 5, 7, 10, 11};
public static void main(String[] args) {
	Map<Integer, Integer> matchedIndexes = new HashMap<>();
	IntStream.range(0, values.length)
			.forEach(x -> IntStream.range(x + 1, values.length)
					.filter(f -> !matchedIndexes.containsValue(f))
					.forEach(y -> {
						if (values[x] + values[y] == DESIRED_SUM)
							matchedIndexes.put(x, y);
						return;
					}));
	matchedIndexes.forEach((x, y) -> System.out.println(values[x] + " " + values[y]));
}
}

 

http://pastie.org/10021488

это выглядит как поиск только пар, а не всех комбинаций, нет?

Опубликовано 50 минут назад

Жопой прочел, хуевый день у меня.

same shit

сейчас с комбинациями попробую

ага

а ещё оно игнорит одинаковые цифры, которые имея разные индексы валидны как разные элементы

Ребят, подкиньте идею для "домашнего" проекта(сайта) ?

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