#include<iostream.h>
#include<math.h>
double a[10];              //用于存儲符號的概率
int n;                     //請輸入單符號信源元素個數
double b[10];              //用于存儲碼字的概率
int k[10];                 //用于存儲Ki的K直
int c[10];                 //用于存儲二進嗎
void input();              //輸入數據函數
void paixi();              //對概率排序
void output();             //輸出函數
void bgailui();            //用于求碼字的概率
void kjisuan();            //用于求Ki的K直
void bbianma();            //用于編碼
void panduan();            //用于對輸入數據判斷，避免符號的總和概率》1
void main()
{
	input();
    panduan();
	paixi();
	output();
    bgailui();
    kjisuan();
    bbianma();
}
void input()
{
	cout<<"請輸入單符號信源元素個數 :\n";
	cin>>n;
	cout<<"請輸入單符號概率  :\n";
	for(int i=1;i<n+1;i++)
		cin>>a[i];
}
void panduan()
{
    double sum=0;
    for(int i=0;i<n+1;i++)
	
			sum+=a[i];
	
	cout<<""<<sum<<endl;
		if(sum==1.0)
			cout<<"將執行下面操作："<<endl;
		else if(sum!=1.0)
		{
			cout<<" 輸入錯誤，請重新輸入     :"<<endl;
			input();
		}
}
            

void paixi()
{
	int i,j,k;
	double x;
	for(i=1;i<n+1;i++)
	{
		k=i-1;
		for(j=i;j<n+1;j++)
			if(a[j]>a[k])
				k=j;
			x=a[i-1];a[i-1]=a[k];a[k]=x;
	}
}
void output()
{
    cout<<"排序后符號概率分布"<<endl;
	for(int i=0;i<n;i++)
			cout<<" "<<a[i];
		 cout<<endl;
}
void bgailui()
{
	b[0]=0;
    for(int i=0;i<n;i++)
   {
	  b[i+1]=b[i]+a[i];
   }
	cout<<"累加概率分布為"<<endl;
   for( i=0;i<n;i++)
   cout<<" "<<b[i];
   cout<<endl;
}
void kjisuan()
{
	for(int i=0;i<n;i++)
	{
		if((-1)*log(a[i])/log(2)==int((-1)*log(a[i])/log(2)))
			k[i]=int((-1)*log(a[i])/log(2));
		else
			k[i]=int((-1)*log(a[i])/log(2))+1;
	}
    cout<<"k為 "<<endl;
	for(i=0;i<n;i++)
		cout<<" "<<k[i];
		cout<<endl;
}
void bbianma()
{
    double x;
	for(int i=0;i<n;i++)
	{
		x=b[i];
        for(int j=0;j<n;j++)
		{
           if(x<=0.5)
		   {
              if(x==int(x))
			    x=0;
		      else
                x=x*2;
                c[j]=int(x);
		   }
		   else if(x>0.5)
		   {
              if(x==int(x))
			    x=0;
			  else
				  x=(x-int(x))*2;
			      c[j]=int(x);
		   }

		 
		}
		cout<<"編碼為"<<endl;
	 for(j=0;j<k[i];j++)
         	cout<<""<<c[j];
		 cout<<endl;
	}
}