#include<iostream>
#include<vector>
#include<iomanip>
#include<cmath>
using namespace std;
typedef vector<int> vt;
void main(){
 vt a,b,c;
 int x,i,j,k; 
 double low,high,mid,t1=1.0;  
 double v[100][11];//存儲個節(jié)點對應坐標。。。
 cout<<"請輸入待編碼的字符串:";
 cin>>x;
 a.push_back(x%10);
 while(x/10!=0){
  a.push_back((x/10)%10);
  x=x/10;
 }
 for(i=1;i<=a.size();i++){
  b.push_back(a[a.size()-i]);
 }//b[i]為字符
 double p[100][10];
 double s[100][10];
 for(i=0;i<=b.size();i++){
  for(j=0;j<10;j++){
   s[i][j]=1;
  }
 }
 for(i=0;i<=b.size();i++){
  for(j=0;j<10;j++){
   if(b[i]==j){    
     s[i+1][j]=s[i][j]+1;
     for(k=i+1;k<b.size();k++)
      s[k+1][j]=s[k][j];
   }
  }
 }
 for(i=0;i<=b.size();i++){
  for(j=0;j<10;j++){
   cout<<s[i][j];
  }
  cout<<endl;
 }
 for(i=0;i<=b.size();i++){
  for(j=0;j<10;j++){
   p[i][j]=s[i][j]/(10+i);
  }
 }
 for(i=0;i<=b.size();i++){
  cout<<"加入第"<<i<<"個元素自適應概率為:"<<endl;
  for(j=0;j<10;j++){  
   cout<<setprecision(5)<<p[i][j]<<" ";
  }
  cout<<endl;
 }
 for(i=0;i<=b.size();i++){
  for(j=0;j<10;j++){
   v[i][0]=0;v[i][10]=1;
   v[i][j+1]=v[i][j]+p[i][j];
  }
 }  
 cout<<'\n'<<endl;
  for(i=0;i<=b.size();i++){
  cout<<"加入第"<<i<<"個元素后對應坐標為:"<<endl;
  for(j=0;j<=10;j++){  
   cout<<setprecision(5)<<v[i][j]<<" ";
  }
  cout<<endl;
 }
  cout<<'\n'<<endl;
  for(i=0;i<b.size();i++){     
    t1=t1*p[i][b[i]];  
 }
 //const int length=(int)(-log(t1)/log(2))+1;
 //cout<<"所需碼長為："<<length<<endl;
 //////////////////////////////////////////////////////////////////
 /////////////////////////以下為編碼部分///////////////////////////
 //////////////////////////////////////////////////////////////////
 low=v[0][b[0]];high=v[0][b[0]+1];
 for(i=1;i<b.size();i++){  
   low=low+(high-low)*v[i][b[i]];
   double temp=(low-v[i][b[i]]*high)/(1-v[i][b[i]]);
   high=temp+(high-temp)*v[i][b[i]+1]; 
 }
 mid=(high+low)/2;
  double result=mid;
  const int length=-log(high-low)/log(2)+1;
  cout<<"所需碼長為："<<length<<endl;
 cout<<setprecision(10)<<low<<'\t'<<high<<'\t'<<mid<<endl;  
 for(i=0;i<length;i++){//轉(zhuǎn)換成二進制
   mid=mid*2;
  if(mid<1){
   c.push_back(0);
   }
  else{
    c.push_back((int)mid);
    mid-=1;
   }
  }
  cout<<"編碼結(jié)果如下："<<endl;
  for(i=0;i<c.size();i++)
   cout<<c[i]; 
  cout<<endl; 
}