Coursera Algorithms 학습 의 길 (1)

소프트웨어 찌꺼기 는 정말 분발 하여 강해 지 려 고 합 니 다. 연 구 를 마 친 날 을 허비 해 서 는 안 됩 니 다. 배 운 찌꺼기 와 같은 데이터 구조 와 알고리즘 을 다시 주 워 야 합 니 다. 화 이 팅 하 세 요 ~ 첫 주 프로 그래 밍 작업 을 여기에 기록 하 세 요. Percolation

public class Percolation {
    int[][]id;
    int n;
     public Percolation(int n)
     {

         // create n-by-n grid, with all sites blocked
         id=new int[n][n];
         this.n=n;
         for(int a=0;afor(int b=0;bid[a][b]=0; 

             }

         }

     }

       public void open(int i, int j){
           // open site (row i, column j) if it is not open already
          id[i-1][j-1]=1;

          if(j1&&i>1)
          {
          if((id[i-1][j]==2)||(id[i][j-1]==2)||(id[i-2][j-1]==2)||(id[i-1][j-2]==2))
          {
              id[i-1][j-1]=2;
          }
          }
          else 
          {
              if(i==1)
              {
                  id[i-1][j-1]=2;
              }
          else if(j==1&&iid[i-1][j]==2)||(id[i][j-1]==2)||(id[i-2][j-1]==2)))
            {
                id[i-1][j-1]=2;
            }
          else if(((j==n&&iid[i][j-1]==2)||(id[i-2][j-1]==2)||(id[i-1][j-2]==2)))||((i==n&&j1)&&((id[i-1][j]==2)||(id[i-2][j-1]==2)||(id[i-1][j-2]==2))))               
             {

                 id[i-1][j-1]=2;
             }
            else if(((i==n&&j==n)&&((id[i-2][j-1]==2)||(id[i-1][j-2]==2))))
                  {

                    id[i-1][j-1]=2;
                  }
          }

       }
       public boolean isOpen(int i, int j) {
           // is site (row i, column j) open?

           if(id[i-1][j-1]>0)
           {
           return true;
           }
           else{
               return false;
           }
       }
       public boolean isFull(int i, int j) {
           // is site (row i, column j) full?
           System.out.println(n);
           System.out.println("i="+i+"j="+j);
           if(id[i-1][j-1]==1)
           {
              if(j1&&i>1)
              {
              if((id[i-1][j]==2)||(id[i][j-1]==2)||(id[i-2][j-1]==2)||(id[i-1][j-2]==2))
              {
                  id[i-1][j-1]=2;
              }
              }
              else 
              {
                  if(i==1)
                  {
                      id[i-1][j-1]=2;
                  }
              else if(j==1&&iid[i-1][j]==2)||(id[i][j-1]==2)||(id[i-2][j-1]==2)))
                {
                    id[i-1][j-1]=2;
                }
              else if(((j==n&&iid[i][j-1]==2)||(id[i-2][j-1]==2)||(id[i-1][j-2]==2)))||((i==n&&j1)&&((id[i-1][j]==2)||(id[i-2][j-1]==2)||(id[i-1][j-2]==2))))               
                 {

                     id[i-1][j-1]=2;
                 }
                else if(((i==n&&j==n)&&((id[i-2][j-1]==2)||(id[i-1][j-2]==2))))
                      {

                        id[i-1][j-1]=2;
                      }
                else if(j==1&&i==n&&(id[i-2][j-1]==2||id[i-1][j]==2))
                {
                    id[i-1][j-1]=2;
                }
              }
           }
           if(id[i-1][j-1]==2)
           {
               return true;
           }
           else{
               return false;
           }

       }
       public boolean percolates()  {
           // does the system percolate?
           for(int a=0;aif(id[n-1][a]==2)
               {
                   return true;
               }
           }
           return false;
       }



}

ProcolationStats

public class PercolationStats {
     double[] p;
     int trials;
     public PercolationStats(int n, int trials) 
     {
         // perform trials independent experiments on an n-by-n grid
         this.trials=trials;
         p=new double[n];
         for(int i=0;inew Percolation(n);
             int a=0;
             while(true)
             {
                 int x=StdRandom.uniform(n)+1;
                 int y=StdRandom.uniform(n)+1;
                 System.out.println(x+" "+y);
                 p1.open(x, y);
                 p1.isFull(x, y);
                 a++;
                 if(p1.percolates())
                 {
                     break;
                 }
             }
             p[i]=(a/n);

         }
     }
       public double mean() 
       {           
           // sample mean of percolation threshold
           return StdStats.mean(p);
       }
       public double stddev(){
           // sample standard deviation of percolation threshold
           return StdStats.stddev(p);
       }
       public double confidenceLo() {
           // low  endpoint of 95% confidence interval
           return mean()-1.96*stddev()/trials;
       }
       public double confidenceHi() {
           // high endpoint of 95% confidence interval
           return mean()+1.96*stddev()/trials;
       }

}

이번 주 는 주로 빠 른 검색, 병합 검색, 트 리 구조 로 저장 되 었 습 니 다. 나중에 나무의 크기 에 따라 최적화 하고 배열 로 트 리 를 저장 하 는 것 이 좋 습 니 다.