首页 > 专题系列 > Java解POJ > POJ 2083 Fractal [解题报告] Java
2013
11-10

POJ 2083 Fractal [解题报告] Java

Fractal

问题描述 :

A fractal is an object or quantity that displays self-similarity, in a somewhat technical sense, on all scales. The object need not exhibit exactly the same structure at all scales, but the same “type” of structures must appear on all scales.

A box fractal is defined as below :
  • A box fractal of degree 1 is simply

    X
  • A box fractal of degree 2 is

    X X

    X

    X X
  • If using B(n – 1) to represent the box fractal of degree n – 1, then a box fractal of degree n is defined recursively as following
    B(n - 1)        B(n - 1)
    
    B(n - 1)
    B(n - 1) B(n - 1)

Your task is to draw a box fractal of degree n.

输入:

The input consists of several test cases. Each line of the input contains a positive integer n which is no greater than 7. The last line of input is a negative integer −1 indicating the end of input.

输出:

For each test case, output the box fractal using the ‘X’ notation. Please notice that ‘X’ is an uppercase letter. Print a line with only a single dash after each test case.

样例输入:

1
2
3
4
-1

样例输出:

X
-
X X
 X
X X
-
X X   X X
 X     X
X X   X X
   X X
    X
   X X
X X   X X
 X     X
X X   X X
-
X X   X X         X X   X X
 X     X           X     X
X X   X X         X X   X X
   X X               X X
    X                 X
   X X               X X
X X   X X         X X   X X
 X     X           X     X
X X   X X         X X   X X
         X X   X X
          X     X
         X X   X X
            X X
             X
            X X
         X X   X X
          X     X
         X X   X X
X X   X X         X X   X X
 X     X           X     X
X X   X X         X X   X X
   X X               X X
    X                 X
   X X               X X
X X   X X         X X   X X
 X     X           X     X
X X   X X         X X   X X
-

解题代码:

//* @author: [email protected]
import java.util.Scanner;
class Main
{
 static StringBuffer sb=new StringBuffer();
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  while(true)
  {
	int a=in.nextInt();
	if(a==-1) break;
	else if(a==1) System.out.println('X');
	else g("",a-1);
	System.out.println("-");
  }
 }


 static void p(int a)
 {
  int t=(int)Math.pow(3, a-1);
  for(int i=0;i< t;i++)
	sb.append(" ");
 }

  static void g(String s,int a)
  {
   if(a==0)
   {
	sb.delete(0, sb.length()+1);
	print(s);
	System.out.println(sb.toString().subSequence(0, sb.lastIndexOf("X")+1));
	return;
    }
	g(s+"A",a-1);
	g(s+"B",a-1);
	g(s+"A",a-1);
		
    }
	

 static void print(String s)
 {
	int l=s.length();
	char c=s.charAt(0);
	if(l==1)
	{
          if(c=='A') sb.append("X X");
	  else sb.append(" X ");
	  return;
	}
	if(c=='A')
	{
	   print(s.substring(1));
	   p(l);
	   print(s.substring(1));
	}
	else 
	{
	   p(l);
	   print(s.substring(1));
	   p(l);
	}
   }
}

  1. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧

  2. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法

  3. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢

  4. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  5. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。

  6. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮