import java.applet.*;
import java.awt.*;
public class Example3_10 extends Applet
{
 public static boolean xishusolve(int[] row,int[] col,double[] value,double[] x,double eps)
  { int i,m=row.length,n=x.length,j,k,l,r;
    int[] p=new int[n];
    double temp,max;
    double[] y=new double[n];
    double[] z=new double[n];
    boolean falg=true;
    for(i=0;i<n;i++)p[i]=i;
    for(i=0;i<n;i++)
    {  //找主元用k，l記主元的行號(hào)列號(hào)，r記主元的位置。
	   max=-1;r=0;k=i;l=i;
	   for(j=0;j<m;j++)
       { if((row[j]>=i)&&(col[j]>=i))
         { temp=Math.abs(value[j]);
           if (temp>max){max=temp;k=row[j];l=col[j];r=j;}
          }
       }
	    if (max<1e-30){return false;}
        //第i行與第k行互換
	    for(j=0;j<m;j++)
	     {if(row[j]==i)row[j]=k;
	      else if(row[j]==k)row[j]=i;}
	    temp=x[i];x[i]=x[k];x[k]=temp;
        //第i行歸一化，順便檢查此行是否對(duì)角占優(yōu)。
          temp=0;
          for(j=r-1;j>=0;j--)
          {if(row[j]!=i)break;
           value[j]/=value[r];temp+=Math.abs(value[j]);}
           for(j=r+1;j<m;j++)
		   {if(row[j]!=i)break;
           value[j]/=value[r];temp+=Math.abs(value[j]);}
          x[i]/=value[r];value[r]=1;
        if(temp>=1)falg=false;
        //第i列和第l列交換
	    for(j=0;j<m;j++)
	    {if(col[j]==i)col[j]=l;
	     else if(col[j]==l)col[j]=i;}
	    k=p[i];p[i]=p[l];p[l]=k;
   }
	    if(!falg)
        {return false; }

	  //jacobi迭代
	 for(i=0;i<n;i++)y[i]=x[i];
	 for(k=0;k<10000;k++)
	 { for(i=0;i<n;i++)z[i]=x[i];
	   for(j=0;j<m;j++)
	   {if (row[j]==col[j])continue;
	    z[row[j]]-=value[j]*y[col[j]];}
      falg=true;
      for(i=0;i<n;i++)
	  if(Math.abs(y[i]-z[i])>=eps){falg=false;break;}
	  if(falg)break;
	  for(i=0;i<n;i++)y[i]=z[i];
	 }
	  //輸出結(jié)果
	  for(i=0;i<n;i++)x[p[i]]=z[i];
	  return true;
	}


  public void paint(Graphics g)
  {int[] row={0,0,1,1,2,2,3,3,3,4,4,5,5,5,6,6,7,7,7};
   int[] col={2,6,1,5,3,7,0,5,7,2,6,0,4,7,1,3,2,5,7};
   double[] value={-1,2,7,-6,2,-4,4,-2,1,6,5,1,-4,2,3,-4,1,4,-2};
   double[] x={4,6,-8,7,27,-13,8,-4};
   double eps=1e-7;
  if( xishusolve(row,col,value,x,eps))
   {for(int i=0;i<8;i++)
    g.drawString("X"+i+"="+x[i],10,i*20+20);}
  else
   g.drawString("矩陣無(wú)法進(jìn)行迭代或矩陣不是對(duì)角占優(yōu)矩陣",10,20);
 }

}