首页 > 专题系列 > Java解POJ > POJ 3173 Parkside’s Triangle [解题报告] Java
2013
11-12

POJ 3173 Parkside’s Triangle [解题报告] Java

Parkside’s Triangle

问题描述 :

Bessie taught the cows to make Parkside’s Triangle. It is generated from two numbers: the size and the seed. The size N (1 <= N <= 20) determines how many rows are in the triangle and the seed S (1 <= S <= 9) determines the first number in the triangle. Here are two examples:

 N=5, S=3                  N=6, S=1  


3 4 6 9 4 1 2 4 7 2 7
5 7 1 5 3 5 8 3 8
8 2 6 6 9 4 9
3 7 1 5 1
8 6 2
3

The first line of any triangle has no blanks at its front.

Analyze the above examples, discover the rule, and write a program that will generate Parkside’s Triangle given any size N (1 <= N <= 20) and any seed S (1 <= S <= 9).

输入:

Line 1: Two space-separated integers: N and S

输出:

Lines 1..N: Parkside’s Triangle as above; no trailing blanks on any line.

样例输入:

5 3

样例输出:

3 4 6 9 4
  5 7 1 5
    8 2 6
      3 7
        8

解题代码:

import java.util.*;  
   
 public class Main {  
   
     public static void main(String[] args) {  
         Scanner cin = new Scanner(System.in);  
           
         String[] str = cin.nextLine().split(" ");  
         int N = Integer.valueOf(str[0]).intValue();  
         int S = Integer.valueOf(str[1]).intValue();  
               
         int[][] Tri = new int[N][N];  
               
         for(int j = 0; j < N; j++)  
         {  
             for(int i = 0; i <= j; i++)  
             {  
                 Tri[i][j] = S;  
                   
                 if(S == 9)  
                     S = 1;  
                 else  
                     S++;  
             }  
         }  
         print(Tri);  
     }  
       
       
     private static void print(int[][] tri)  
     {  
         for(int i = 0; i < tri.length; i++)  
         {  
             for( int j = 0; j < tri.length - 1; j++)  
             {  
                 if(tri[i][j] < 1 || tri[i][j] > 9)  
                     System.out.print(" ");  
                 else  
                     System.out.print(tri[i][j]);  
                 System.out.print(" ");  
                   
             }  
             System.out.println(tri[i][tri.length -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. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  3. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  4. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;