recursive algoritma

[Tcpip]

bir soru var, ugrastım da çözemedim belki recursive ile arası iyi olan vardır.

using "1 2 3 4 5 6 7 8 9 10" integers number make a set that sum 30. how many set you can do.

örneğin 30 tane 1 olabilir
yada 28 tane 1 + 1 tane 2
yada 27 tane 1 + 1 tane 3
yada 26 tane 1 + 2 tane 2
yada 26 tane 1 + 1 tane 4

ağaç yapısı ile yada recursive fonksiyon yazarak çözülebileceğine inanıyorum da bir türlü kafamı toplayamadım.

[Kojiroh]

Bizim bu dönem bi derste bu tarz şeyler işlenmişti aslında, hatta sunum konum da buydu. Şu an evde değilim o yüzden belgeleri bulamıyorum ama eve gidince bulur yazarım. 4-5 tane yöntem var bunun için, recursiveler miydi tam hatırlamıyorum da vardır mutlaka aralrında bi tane.

[SpiderS_DangeR]

Ben senin tam dediğini değilde şöyle birşey yazmıştım, hatta recursion kullanarak.

Elimizde iki sayı var, mesela 10 ve 5, P(10,5) diyelim. Yazdığım fonksiyon 10 toplamına 5 sayının toplamı olarak kaç farklı şekilde ulaşılabileceğini buluyordu, hatta konusunu da buldum

http://forum.paticik.com/read.php?6,4460948,page=1

ilk sayfanın en sonunda kodu da yazmışım. Belki bunu uyarlayarak falan bişeyler yapabilirsin

[Kojiroh]

Ben de kitaptaki metodlardan birini hatırladım.
Bi n sayısı için (n-1, 1) ikilisinden başlıyosun, (1, 1, 1...) olana kadar gidiyosun. Her adımda en soldaki sayı hariç tüm sayıları 1 yapmaya çalışıyosun. Onu yaptıktan sonra en soldaki sayıyı bi azaltıp, hemen sağındaki sayıyı 1 artırıyosun.

Örneğin 8 var elimde. 7 + 1 şeklinde açıyorum ilk

	7 1

	

Şimdi en soldaki hariç tek sayı 1 olduğu için en soldaki sayıyı 1 azaltıp hemen sağındakini 1 artırıyorum

	6 2

	

En soldaki hariç tümünü 1 yapmam lazım,

	6 1 1

	

En soldakini 1 azaltıp sağındakini artırıyorum

	5 2 1

	

1'lere açıyorum

	5 1 1 1

	

Devam...

	4 2 1 1

	4 1 1 1 1

	3 2 1 1 1

	3 1 1 1 1 1

	2 2 1 1 1 1

	2 1 1 1 1 1 1

	1 1 1 1 1 1 1 1

	

Toplam 12 farklı şey oldu. Bunun gibi. Örnek kodu evde ama, onu anca akşam verebilirim :P

Edit: Dur ya eksik hatırlamışım, 4 3 1 falan yok bunda. Biraz daha zorliim bakiim.

[SpiderS_DangeR]

ahhasdf yalın

[Tcpip]

evet, güzel yaklaşım teşekkür ederim.

[Mirage]

f(n) fonksiyonu n tane sayıyı hangi şekillerde yazabileceğini gösteren, sayı dizilerinden oluşan bir küme versin.

addToAll(e, s) ise e elemanını s kümesindeki tüm dizilerin başına ekleyen bir fonksiyon olsun. Örnek:

	addToAll(1, {[1, 1], [2]}) = {[1, 1, 1], [1, 2]}

	

U ise permutasyonları eleyen bir küme birleşim operatörü olsun. Örnek:

	{[1, 2]} U {[2, 1]} = {[1, 2]}

	

	       { {[1]}, if n = 1

	f(n) = { 

	       { {[n]} U ( U i in (1 to n-1) addToAll(i, f(n - i)) ), otherwise

	

Örnek:

	f(2) = {[2]} U addToAll(1, f(1))

	f(2) = {[2]} U {[1, 1]}

	f(2) = {[2], [1, 1]}

	

	f(3) = {[3]} U ( addToAll(1, f(2)) U addToAll(2, f(1)) )

	f(3) = {[3]} U {[1, 2], [1, 1, 1]} U {[2, 1]}

	f(3) = {[3], [1, 2], [1, 1, 1]}

	

	f(4) = {[4]} U ( addToAll(1, f(3)) U addToAll(2, f(2)) U addToAll(3, f(1)) )

	f(4) = {[4]} U {[1, 3], [1, 1, 2], [1, 1, 1, 1]} U {[2, 2], [2, 1, 1]} U {[3, 1]}

	f(4) = {[4], [1, 3], [1, 1, 2], [1, 1, 1, 1], [2, 2]}

	

Aradığın fonksiyon ise f(n)'in eleman sayısı.

[Ceday]

nie 1 ekliosun ki hep?

n>1 icin

f i asagıdaki sekilde tanımlamak lazım:

total = 0;
for(int k=1; k<11; k++) {
total += (n-k > 0 ? f(n-k) : 0);
}
return total;

Mirage said:

	       { {[1]}, if n = 1

	f(n) = { 

	       { {[n]} U ( U i in (1 to n-1) addToAll(i, f(n - i)) ), otherwise

	

[Mirage]

1 eklemiyorum ki? edik: Bana degilmis sanirim soru. edik2: yok banaymis galiba kafam karisti :p

[Tcpip]

Link list kullanarak iteratif olarak çözdüm.
Bu arada cevap 3912.
çözen olursa karşılaştırabiliriz.

[Ceday]

benim yazdıgımda da yanlıslık var aslında.
neyse bakarım evde :)

[Mirage]

Canım sıkıldı yukarda belirttiğim algoritmayı javada yazdım. Yalnız süre karesel arttığı için 25'ten sonrası değerler için aşırı uzun sürmeye başladı. 30 için 2-3 dakkada bile cevap bulamadı. Ufak bir cache yazınca sonucu 5604 olarak buldu:

Cache'siz

	import java.util.ArrayList;

	import java.util.Collections;

	import java.util.HashSet;

	import java.util.List;

	import java.util.Set;

	

	public class Paticik {

	

		public static Set<List<Integer>> f(int n) {

			Set<List<Integer>> results = new HashSet<List<Integer>>();		

			List<Integer> possibleValues = new ArrayList<Integer>();

			possibleValues.add(n);

			results.add(possibleValues);

			

			if (n > 1) {			

				for (int i = 1; i < n; i++) {

		            		Set<List<Integer>> possibleValuesForNMinus1 = f(n - i);

					addToAll(i, possibleValuesForNMinus1);

					results.addAll(possibleValuesForNMinus1);

				}

			}

			

			return results;

		}

		

		public static void addToAll(int n, Set<List<Integer>> set) {

			for (List<Integer> list : set) {

				list.add(n);

				Collections.sort(list);

			}

		}

		

		public static void main(String[] args) {

			Set<List<Integer>> f = f(30);

			System.out.println(f);

			System.out.println(f.size());

		}

		

	}

	

Cache'li

	import java.util.ArrayList;

	import java.util.Collections;

	import java.util.HashMap;

	import java.util.HashSet;

	import java.util.List;

	import java.util.Map;

	import java.util.Set;

	

	public class PaticikCached {

		

		private static Map<Integer, Set<List<Integer>>> cache = new HashMap<Integer, Set<List<Integer>>>();

	

		public static Set<List<Integer>> f(int n) {

			if (cache.containsKey(n)) {

				return cache.get(n);

			}

			

			Set<List<Integer>> results = new HashSet<List<Integer>>();		

			List<Integer> possibleValues = new ArrayList<Integer>();

			possibleValues.add(n);

			results.add(possibleValues);

			

			if (n > 1) {			

				for (int i = 1; i < n; i++) {

		            		Set<List<Integer>> possibleValuesForNMinus1 = clone(f(n - i));

					addToAll(i, possibleValuesForNMinus1);

					results.addAll(possibleValuesForNMinus1);

				}

			}

			

			cache.put(n, results);

			return results;

		}

		

		public static void addToAll(int n, Set<List<Integer>> set) {

			for (List<Integer> list : set) {

				list.add(n);

				Collections.sort(list);

			}

		}

		

		private static Set<List<Integer>> clone(Set<List<Integer>> set) {

	        	Set<List<Integer>> setClone = new HashSet<List<Integer>>();

	        	for (List<Integer> list : set) {

	            		List<Integer> listClone = new ArrayList<Integer>(list.size());

	            		for (int i : list) {

	                		listClone.add(i);

	            		}

	            		setClone.add(listClone);

	        	}

	        	return setClone;

	    	}

		

		public static void main(String[] args) {

			Set<List<Integer>> f = f(30);

			System.out.println(f);

			System.out.println(f.size());

		}

		

	}

	

[Ceday]

3590 cıktı benimkinde :)
3 ayrı class var, ayrı ayrı yapıstırdım.

edit: Node classını unutmusum, 4 class var.

Code

	

	public class Node {

		

		public int value;

		public int count;

		public Node(int value, int count) {

			super();

			this.value = value;

			this.count = count;

		}

	

	}

	

	public class Test {

	

		/**

		 * @param args

		 */

		public static void main(String[] args) {

			NodeOrder nodeOrder = new NodeOrder(30);

			nodeOrder.findAllPossibleList();

			nodeOrder.writePossibleList();

	

		}

	

	}

	

	

	import java.util.ArrayList;

	import java.util.Collections;

	import java.util.List;

	

	

	public class NodeOrder {

		

		private int maxInput = 10;  

		private List<NodeList> possibleNodeList = new ArrayList<NodeList>();

		

		public NodeOrder(int n){

			List<Node> nodeList = new ArrayList<Node>();

			nodeList.add(new Node(1, n));

			possibleNodeList.add(new NodeList(nodeList));

		}

		

		public void findAllPossibleList() {

			int size = possibleNodeList.size();

			iterate();

			while(size != possibleNodeList.size()){

				size = possibleNodeList.size();

				iterate();

			}

		}

		

		public void writePossibleList(){

			System.out.println(possibleNodeList.size());

			for(NodeList nodeList : possibleNodeList){

				for(Node node : nodeList.nodeList){

					if (node.count == 0)

						continue;

					for(int k=0; k<node.count; k++){

						System.out.print(node.value);

					}

				}

				System.out.println();

			}

		}

		

		private void iterate(){

			List<NodeList> nextStates = new ArrayList<NodeList>();

			for(NodeList nodeList : possibleNodeList) {	

				if (nodeList.iterated)

					continue;

				for(int k=0; k<nodeList.nodeList.size(); k++){

					Node first = nodeList.nodeList.get(k);

					if (first.count == 0)

						continue;

					if (first.count > 1) {

						int newValue = first.value * 2;

						if (newValue <= maxInput) {

							nextStates.add(createNewState(nodeList.nodeList, first, first));

						}

					}

					for(int m=k+1; m<nodeList.nodeList.size(); m++){

						Node second = nodeList.nodeList.get(m);

						if (second.count == 0)

							continue;

						int newValue = first.value + second.value;

						if (newValue <= maxInput){

							nextStates.add(createNewState(nodeList.nodeList, first, second));

						}

					}

				}

				nodeList.iterated = true;

				

			}

			

			for(NodeList nodeList : nextStates){

				if (!isExistNodeList(nodeList)){

					possibleNodeList.add(nodeList);

				}

			}

		}

		

		private boolean isExistNodeList(NodeList nodeList){

			String identifier = nodeList.getIdentifier();

			for(NodeList nodeListPoss : possibleNodeList){

				if (nodeListPoss.getIdentifier().equals(identifier))

					return true;

			}

			return false;

		}

		

		private static List<Node> clone(List<Node> nodeList){

			List<Node> newList = new ArrayList<Node>();

			for(Node node : nodeList){

				newList.add(new Node(node.value, node.count));

			}

			

			return newList;

		}

		

		private NodeList createNewState(List<Node> nodeListOld, Node first, Node second){

			

			int newValue = first.value + second.value;

			boolean foundNewValue = false;

			

			List<Node> nodeList =  clone(nodeListOld);

			for(Node node : nodeList) {

				if (node.value == first.value){

					node.count--;

				}

				if (node.value == second.value){

					node.count--;

				}

				if (node.value == newValue){

					foundNewValue = true;

					node.count++;

				}

			}

			if (!foundNewValue){

				nodeList.add(new Node(newValue, 1));

			}

			

			return new NodeList(nodeList);

			

		}

	

	}

	

	import java.util.ArrayList;

	import java.util.Collections;

	import java.util.Comparator;

	import java.util.List;

	

	

	public class NodeList {

		

		public List<Node> nodeList = new ArrayList<Node>();

		public boolean iterated = false;

		

		public NodeList(List<Node> nodeList){

			this.nodeList = nodeList;

			Collections.sort(nodeList, new Comparator<Node>() {

				

				@Override

				public int compare(Node arg0, Node arg1) {

					return new Integer(arg0.value).compareTo(new Integer(arg1.value));

				}

			});

		}

		

		public String getIdentifier() {

	

			

			StringBuffer identifier = new StringBuffer();

			for(Node node : nodeList) {

				if (node.count == 0)

					continue;

				identifier.append(node.count).append(node.value);

			}

			

			return identifier.toString();

		}

	

	}

	

	

	

[nakerebanarimasen]

Tcpip said:

Link list kullanarak iteratif olarak çözdüm.
Bu arada cevap 3912.
çözen olursa karşılaştırabiliriz.

3912 gerçek cevap mı senin bulduğun mu?

[Ceday]

dogrusunu ben yazdım ya :p

[nakerebanarimasen]

Ceday said:

dogrusunu ben yazdım ya :p

örneğin "9 9 9 1 1 1" ile "9 1 1 1 9 9 9" farklı mı aynı mı? aynıysa 165 tane ;)

[Ceday]

aynı dicem de yanlıs yazmıssın sanırım :)

[Tcpip]

Doğru olup olmadığını listeye dökerek anlayabilirsiniz.
Ben listeye döktüm eksik yada fazla yoktu.

Gerçi kabul edildi çözüm, tam doğru olup olmadığına bakmıyorlar sanırım :)