硬币算法优化

Question

如何在不超出调用堆栈大小的情况下处理递归调用？

这个问题在这里回答了Maximum call stack size exceeded error，但对我没有帮助。这可能对别人有帮助。

算法提示是一点点漫长的，但对于那些你被确定：coin algorithm

我的代码可能不会试图满足所有要求，但不管我想什么，我有一些投入。

var gameSetup = { 
     coins: [2,333,4,11,99,20,10], 
     minOdds: 1, 
     maxOdds: 100000 
} 
function game(gs) { 
     this.minOdds = gs.minOdds; 
     this.maxOdds = gs.maxOdds; 

     var coinArray = gs.coins; 
     var coinArrayLength = coinArray.length; 
     var indicesToSplice = []; 

     var gameResults = { 
       turns: 0, 
       score: 0 
     } 

     var gameFunctions = { 
       getTurns: function() { 
         return gameResults.turns; 
       }, 
       setTurns: function() { 
         ++gameResults.turns; 
       }, 
       setScore: function(lcv,rcv) { 
         var score = lcv * rcv; 
         gameResults.score += score; 

       }, 
       getScore: function() { 
         return gameResults.score; 

       }, 
       generateFlips: function() { 
         return generateFlips.getRandomNumbersInclusive(); 
       } 

     } 
     var generateFlips = (function() { 
       var flips = []; 
         return { 
           getRandomNumbersInclusive: function() { 
             flips = []; 
             for(i=0; i < coinArrayLength; i ++){ 
               var currentFlip = Math.floor(Math.random() * (maxOdds - minOdds + 1)) + minOdds; 
               flips.splice(0,0,currentFlip); 
             } 
           return flips; 
           } 
         } 
     })(); 
     (function takeTurn(coinArrayLength) { 
       var flips = gameFunctions.generateFlips(); 


       flips.forEach(function(i, index) { 
         if(i == maxOdds) { 
           var leftOfIndex = flips[index-1]; 
           var rightOfIndex = flips[index +1]; 
           if(typeof leftOfIndex === 'undefined' || typeof rightOfIndex === 'undefined') { 

           } else { 
             indicesToSplice.splice(0,0,index); 
             var leftCoinValue = coinArray[index-1]; 
             var rightCoinValue = coinArray[index+1]; 
             gameFunctions.setScore(leftCoinValue,rightCoinValue); 
           } 

         } 

       }); 



       if(indicesToSplice.length > 0) { 
         indicesToSplice.forEach(function(i){ 
           coinArray.splice(i,1); 
           coinArrayLength = coinArray.length; 
         }); 
       } 
       indicesToSplice = []; 
       gameFunctions.setTurns(); 

       if(coinArrayLength > 2) { 
         takeTurn(coinArrayLength); 
       } else { 
         return; 

       } 

     })(coinArrayLength); 


} 
game(gameSetup); 

Answer 1

How do I handle the recursive call without exceeding the call stack size?

你不让它递归。除了coinArrayLength之外，没有需要保存的状态，这可以通过while循环来完成。

while (coinArrayLength > 2) { 

    var flips = gameFunctions.generateFlips(); 

    flips.forEach(function(i, index) { 
     if(i === maxOdds) { 
      var leftOfIndex = flips[index-1]; 
      var rightOfIndex = flips[index +1]; 
      if(typeof leftOfIndex === 'undefined' || typeof rightOfIndex === 'undefined') { 


      } else { 
       indicesToSplice.splice(0,0,index); 
       var leftCoinValue = coinArray[index-1]; 
       var rightCoinValue = coinArray[index+1]; 
       gameFunctions.setScore(leftCoinValue,rightCoinValue); 
      } 
     } 
    }); 

    if(indicesToSplice.length > 0) { 
     indicesToSplice.forEach(function(i){ 
      coinArray.splice(i,1); 
      coinArrayLength = coinArray.length; 
     }); 
    } 
    indicesToSplice = []; 
    gameFunctions.setTurns(); 
} 

您的代码充满了没有目的的IIF。该gameFunctions.generateFlips功能可以归结为：

function generateFlips() { 
    var flips = []; 
    for (var i = 0; i < coinArrayLength; i++) { 
     var currentFlip = Math.floor(Math.random() * (maxOdds - minOdds + 1)) + minOdds; 
     flips.unshift(currentFlip); 
    } 
    return flips; 
} 

然而，你必须将其与2条return语句，一个IIF内，存储在gameFunctions对象上写。把事情简单化。