ploymod2.cpp

多项式模多项式算法

 #include <iostream>
#include <string.h>
using namespace std;
// The method of ploynomal minus .
//
int ployMinus(int first[], int &firstN, int second[] ,int secondN){
    if(firstN <secondN ) return 0;
     int divAnswer  = first[firstN]/second[secondN];
     int i;

     for(i = firstN;i>=firstN - secondN ; i--){
        first[i]-=divAnswer*second[i-firstN+secondN];
     }
     

     for(i = firstN;i>=0;i--) if(first[i]!=0) break;
     firstN =i;
     
     
     return divAnswer;
 }

// first[] ---原多项式。
// firstN ----原多项式的最高次数。
// second[] ---模多项式。
// secondN ----模多项式的最高次数。
// divAnswer[] = first[] / second[].
// modAnswer[] = first[] % second[].
// divN, 除之后的最高次。 divN = -1 . 表示不用除。
// modN, 模之后的最高次。 modN = -1 . 表示模的结果为0. 
 void ployMod(int first[], int firstN, int second[] ,int secondN,
         int modAnswer[], int &modN, int divAnswer[], int &divN){
          // 设divN = -1.
         divN = -1;
         // 若原多项式的最高次少于模多项式则。
         modN = firstN;
         int i;
         for(i=0;i<=modN;i++)
         {
                modAnswer[i]=first[i];
         }    

         if(firstN >=secondN){
             divN = firstN - secondN;
             for(i = divN ;i>=0;i--){
                 divAnswer[i] = ployMinus(modAnswer, modN, second, secondN);
             }
         }
        return ;
 }
 
int main()
{
      int first[] = {-1,0,0,1};
      int second[] = {0,1};
      int firstN = 3;
      int secondN =1;
      int divAnswer[100]={0};
      int modAnswer[100]={0};
      
      int divN, modN;    
      ployMod(first, firstN, second, secondN, modAnswer, modN, divAnswer, divN);
      
      ////////////////////////////////////////////////////////////
      cout<<"modN : " <<modN<<endl;
      cout<<"modAnswer : "<<endl;
      cout<<"[";
      if(modN == -1){
            cout<<"0";
            }else {
      for(int i=0;i<=modN;i++){
            cout<<modAnswer[i]<<", ";
            }
        }
      cout<<"]"<<endl;
      
      ////////////////////////////////////////////////
      cout<<"divN : " <<divN<<endl;
      cout<<"divAnswer : "<<endl;
      cout<<"[ ";
      if(divN == -1){
            cout<<"no need to div."<<endl;
            }else {
      for(int i=0;i<=divN;i++){
            cout<<divAnswer[i]<<", ";
            }
        }
      cout<<"]"<<endl;
      ///////////////////////////////////////////////////////
      system("pause");
}