2

配列Aが与えられたとすると{5, 5, 4, 3, 7}、で操作{*, /, + -}を使用し5, 5, 4, 3、結果をとして取得するとし7ます。可能であれば、答えを印刷してください。そうでない場合は、return 0。

Answer : 5 * 5 - 4 / 3 = 7。

私は再帰、ブルートフォースを使用してこれを解決し、すべてのケースをチェックしました。

私のコード：

void check_result(int* arr, int size, char* op, int depth, int result, int val)
{
    if(depth==size)
    {
        if(val==result)
        {
             // call function to print pattern of op[]
        }
        return ;
    }
    else
    {
        op[depth]='+';
        check_result( arr+1, size, op, depth+1, result, val + *arr );

        op[depth]='-';
        check_result( arr+1, size, op, depth+1, result, val - *arr );

        op[depth]='*';
        check_result( arr+1, size, op, depth+1, result, val * (*arr) );

        op[depth]='/';
        if( *arr )
            check_result( arr+1, size, op, depth+1, result, val / (*arr) );
    }
}

時間がかかるので、この質問のダイナミックなアプローチを教えてくださいO(4^n)。

4

1 に答える 1

1

状態はである必要がありますDP[position][currentValue]。positionこれは、対応している場合に必要な結果を達成できるかどうかを意味しますcurrentValue。

boolean rec(int position, int currentValue)
{
   if (position == lastPosition)
   {
      return currentValue == neededResult;
   } 

   if (computed[position][currentValue]) return DP[position][currentValue]; 

   boolean can = false; 
   int nextNumber = numbers[position + 1];

   //Try every operation here and call rec again
   can |= rec(position + 1, currentValue + nextNumber);
   can |= rec(position + 1, currentValue - nextNumber);
   can |= rec(position + 1, currentValue * nextNumber);
   can |= rec(position + 1, currentValue / nextNumber);

   DP[position][currentValue] = can;
   computed[position][currentValue] = true;
   return can;
}

その後、別の方法で結果を復元できます。

   void restore(int position, int currentValue)
    {
       if (position == lastPosition) return;

       if (DP[position + 1][currentValue + nextNumber]) 
       { 
          cout << " + ";          
          restore(position + 1, currentValue + nextNumber);
       }
       else
       if (DP[position + 1][currentValue - nextNumber]) 
       { 
          cout << " - ";          
          restore(position + 1, currentValue - nextNumber);
       }
       else
       if (DP[position + 1][currentValue * nextNumber]) 
       { 
          cout << " * ";          
          restore(position + 1, currentValue * nextNumber);
       }
       else
       if (DP[position + 1][currentValue / nextNumber]) 
       { 
          cout << " / ";          
          restore(position + 1, currentValue / nextNumber);
       }
    }

PSこれは擬似コードのみです。エラーや見落とされたコーナーケースがあるかもしれません。

于 2012-08-30T11:50:28.880 に答える