首页 > 专题系列 > Java解POJ > POJ 1166 The Clocks [解题报告] Java
2013
11-09

POJ 1166 The Clocks [解题报告] Java

The Clocks

问题描述 :

|-------|    |-------|    |-------|

| | | | | | |
|---O | |---O | | O |
| | | | | |
|-------| |-------| |-------|
A B C

|-------| |-------| |-------|
| | | | | |
| O | | O | | O |
| | | | | | | | |
|-------| |-------| |-------|
D E F

|-------| |-------| |-------|
| | | | | |
| O | | O---| | O |
| | | | | | | |
|-------| |-------| |-------|
G H I
(Figure 1)



There are nine clocks in a 3*3 array (figure 1). The goal is to return all the dials to 12 o’clock with as few moves as possible. There are nine different allowed ways to turn the dials on the clocks. Each such way is called a move. Select for each move a number 1 to 9. That number will turn the dials 90′ (degrees) clockwise on those clocks which are affected according to figure 2 below.
Move   Affected clocks


1 ABDE
2 ABC
3 BCEF
4 ADG
5 BDEFH
6 CFI
7 DEGH
8 GHI
9 EFHI
(Figure 2)

输入:

Your program is to read from standard input. Nine numbers give the start positions of the dials. 0=12 o’clock, 1=3 o’clock, 2=6 o’clock, 3=9 o’clock.

输出:

Your program is to write to standard output. Output a shortest sorted sequence of moves (numbers), which returns all the dials to 12 o’clock. You are convinced that the answer is unique.

样例输入:

3 3 0
2 2 2
2 1 2

样例输出:

4 5 8 9

解题代码:

/* @author: */
import java.util.Scanner;
public class Main{
 public static void main(String args[]){
  Scanner sc=new Scanner(System.in);
  int arr[]=new int[9];
  int ans[]=new int[9];
  int i=0;
  for(i=0;i< 9;i++)
    arr[i]=sc.nextInt();
  int a1,a2,a3,a4,a5,a6,a7,a8,a9,cnt;
  int u[]=new int[9];
  int min=100;
  for(a1=0;a1< 4;a1++)
   for(a2=0;a2< 4;a2++)
    for(a3=0;a3< 4;a3++)
     for(a4=0;a4< 4;a4++)
      for(a5=0;a5< 4;a5++)
	for(a6=0;a6< 4;a6++)
	 for(a7=0;a7< 4;a7++)
	  for(a8=0;a8< 4;a8++)
	   for(a9=0;a9< 4;a9++)
          {
	     cnt=a1+a2+a3+a4+a5+a6+a7+a8+a9;

            u[0]=arr[0]+a1+a2+a4;
            u[1]=arr[1]+a1+a2+a3+a5;
	     u[2]=arr[2]+a2+a3+a6;
            u[3]=arr[3]+a1+a4+a5+a7;
            u[4]=arr[4]+a1+a3+a5+a7+a9;
            u[5]=arr[5]+a3+a5+a6+a9;
            u[6]=arr[6]+a4+a7+a8;
            u[7]=arr[7]+a5+a7+a8+a9;
            u[8]=arr[8]+a6+a8+a9;
            for(i=0;i<9;i++)
		if(u[i]%4!=0)break;
		  if(i==9&&cnt< min)
		  {
		   ans[0]=a1;
		   ans[1]=a2;
		   ans[2]=a3;
		   ans[3]=a4;
		   ans[4]=a5;
		   ans[5]=a6;
		   ans[6]=a7;
		   ans[7]=a8;
		   ans[8]=a9;
		   min=cnt;
		  }
	   }
         boolean bb=false;
	  for(i=0;i< 9;i++)
	  {
	   if(ans[i]==0) continue;
	    for(int j=0;j< ans[i];j++)
	    {
	     if(bb) System.out.printf(" ");
	     bb=true;
	     System.out.printf("%d",i+1);
	   }
	}
    }
}

  1. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }

  2. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

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

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