由拼写自己的名字谈谈分治算法
问题引入
最近,在Quora上看到了一道有趣的问题:How do I print my name 1000 times in Java without looping?(我要怎么样不用循环来输出自己的名字呢?)
解决方法
1.循环
第一眼还没有看到without looping时,我觉得这个无疑是一个十分简单的问题,只需要用1000个循环就可以解决了
public static void main(String[] args){ for(int i=0;i System.out.println("Boyn"); } }
这样看来,似乎并不是什么难事嘛!
2.递归
再仔细地读一下,发现后面有一个限定的条件为without looping,稍微思索了一会,想到了递归,只要限定好了边界条件,递归完全是可以当作循环来使用的.
public int i = 0; public static void main(String[] args){ Print(); } public static void Print(int i){ if(i System.out.println("Boyn"); Print(i); }else{ System.exit(0); } }
但是,递归也有它的缺点,递归由于是函数调用自身,而函数调用是有时间和空间的消耗的:每一次函数调用,都需要在内存栈中分配空间以保存参数、返回地址以及临时变量,而往栈中压入数据和弹出数据都需要时间.在打印1000遍的时候不会产生栈溢出,如果是10w遍,100w遍呢?
3.分治
这个时候,就引出了分治这个概念了.在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础,如排序算法(快速排序,归并排序),傅立叶变换(快速傅立叶变换)…… 分治策略是:对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。 那么根据分治的思想,我们可以写出如下的方法
public class Names { public void p1000() { p300(); p300(); p300(); p100(); } public void p300() { p100(); p100(); p100(); } public void p100() { p30(); p30(); p30(); p10(); } public void p30() { p10(); p10(); p10(); } public void p10() { p3(); p3(); p3(); p1(); } public void p3() { p1(); p1(); p1(); } public void p1() { System.out.println("Boyn"); } public static void main(String [] args) { new Names().p1000(); } }
在这里,首先将1000次分解成了3个300次和1个100次,将一个300次分解成了1个100次..... 可以看到,这样子调用,可以有效地避免了栈溢出的问题,同时,调用函数更少,也让时间进一步减小了.
4.其他方法
在Quora上有着对于该问题的Answer Wiki: Different solutions have been proposed:(提交的不同解法)
Recursion: Using a function that calls itself with a decrementing parameter counting the times it still has to call itself(递归,用一个有用来计数的递减参数的调用自身的方法)
Nested functions: Using functions that call subfunctions an arbitrary amount of times so that the product of all of them equals 1000 (for example 10_10_10)(嵌套函数:使用任意次数调用子函数的函数使它们的总和等于1000)
String concatenation: Creating a string of 1000 identical characters and using the replace function on them, for example through(创建一个重复1000次的字符串)
Conversing a just initialized char array[1000] to String, knowing that it initializes with “\0” for each character
Using the replace function multiple times on its result, similar to the nested function approach
Using Collections.nCopies()
Using Arrays.parallelSetAll()
Using IntStream.mapToObj().forEach()
Semantics: Understanding the task as needing to print “my name 1000 times in Java without looping”(个人认为这个是一个trick,打印出"用Java我的名字一千次没有循环")
Scheduling
Using the loop abilities of the console, just running the file 1000 times
Letting a class constructors print and then creating 1000 objects of this class. This uses the java-specifity that an array of such objects gets initialized directly at the declaration of the array.
Using GoTo Statements (not possible in Java)
Just writing the statement 1000 times (using copy&paste)