×

Loading...
Ad by
Ad by

@Calgary

用JAVASCRIPT写了个测试算法(其实也没什么算法).仅供参考而已.

leoxxll(leoxxll)
本文发表在 rolia.net 枫下论坛<HTML>
<head>
<script lang="javascript">
var strIndex = "";
var strInput;
var targetNumber;
var strTemp = "";
var nInd = 0;

function getNextNumber(N, a, b, m){
for(var i=m; i<=N-(b-a+1); i++){
strIndex += i;

if(a==b){
//Got the indexes
document.getElementById("output").innerHTML += (strIndex + ": ");
//insert '+' based on the indexes
strTemp = strInput;
for(var j=strIndex.length-1; j>=0; j--){
nInd = parseInt(strIndex.charAt(j));
strTemp = strTemp.substr(0, nInd) + '+' + strTemp.substring(nInd, strTemp.length);
}
document.getElementById("output").innerHTML += (strTemp + "<BR>");

//
if (eval(strTemp) == targetNumber) alert("Got it! " + strTemp + "=" + targetNumber + "\nResult: " + b);

strIndex = strIndex.substr(0, strIndex.length-1);
}else if(a<b){
getNextNumber(N, a+1, b, i+1);
}
}

strIndex = strIndex.substr(0, a-2);
}

function test(){
document.getElementById("output").innerHTML ="";

strInput = document.getElementById('txtString').value;
targetNumber = parseInt(document.getElementById('txtNumber').value);

for (var k=1; k<strInput.length; k++){
getNextNumber(strInput.length, 1, k, 1);
}
}
</script>
</head>

<body>
<form>
<table>
<tr>
<td>Digit String:<input type=text name=txtString id=txtString size=20></td>
<td>Target Number:<input type=text name=txtNumber id=txtNumber size=20></td>
</tr>
<tr>
<td>&nbsp;</td>
<td><input type=button name=btnTest value=" Do It " onclick="test();"></td>
</tr>
<tr>
<td colspan=10><div id=output style="width:200px; height:200px; overflow:auto"></div></td>
</tr>
</table>
</form>
</body>

</HTML>更多精彩文章及讨论，请光临枫下论坛 rolia.net
(#2919123@0)
Last Updated: 2006-4-21
This post has been archived. It cannot be replied.
Report

Replies, comments and Discussions:

  • 工作学习 / 专业技术讨论 / 有会这个算法的吗 -whereami(whatever); 2006-4-20 {1527} (#2918348@0)
    本文发表在 rolia.net 枫下论坛We have a string of digits, find the minimum number of additions required for the string to equal some target number. Each addition is the equivalent of inserting a plus sign somewhere into the string of digits. After all plus signs are inserted, evaluate the sum as usual. For example, consider the string "12" . With zero additions, we can achieve the number 12. If we insert one plus sign into the string, we get "1+2", which evaluates to 3. So, in that case, given "12", a minimum of 1 addition is required to get the number 3. As another example, consider "303" and a target sum of 6. The best strategy is not "3+0+3", but "3+03". You can do this because leading zeros do not change the result.

    Write a class SimpleSums that contains the method minMSums, which takes a String numbers and an int sum. The method should calculate and return the minimum number of additions required to create an expression from numbers that evaluates to sum. If this is impossible, return -1.
    Examples
    0)
    "99999"

    45


    Returns: 4

    In this case, the only way to achieve 45 is to add 9+9+9+9+9. This requires 4 additions.

    1)
    "1110"
    3
    Returns: 3

    Be careful with zeros. 1+1+1+0=3 and requires 3 additions.
    2)
    "0123456789"
    45
    Returns: 8

    3)
    "99999"
    100

    Returns: -1
    4)
    "382834"
    100

    Returns: 2

    There are three ways to get 100. They are 38+28+34, 3+8+2+83+4 and 3+82+8+3+4. The minimum required is 2.
    5)
    "9230560001"
    71

    Returns: 4更多精彩文章及讨论，请光临枫下论坛 rolia.net
    • any performance concern? -ice(食言而肥); 2006-4-20 (#2918372@0)
    • Seems like dynamic programming -canadiantire(轮胎-M.I.N.K.); 2006-4-21 (#2918398@0)
      • agree -yuanzidan(原子弹); 2006-4-21 (#2919160@0)
    • 实际上又是一个排列组合的问题 -binghongcha76(一只大猫); 2006-4-21 (#2918717@0)
    • 看着很象大学的作业啊. -leoxxll(leoxxll); 2006-4-21 {171} (#2918750@0)
      似乎不难啊,既然string digits的顺序不变,就没有排列的问题,单纯组合而已.甚至组合都不用,直接把从 0 到 字符长 - 1 个'+' 插入到不同位置,直到找到 target number. 我想得太简单了?
      • 自己实际的动手编编程序，就知道想得是不是太简单了 -binghongcha76(一只大猫); 2006-4-21 (#2918772@0)
        • 恩.道理的确简单,实现随不容易,但至少有思路了.反正闲着.用JAVASCRIPT写写看.呵呵.. -leoxxll(leoxxll); 2006-4-21 (#2918791@0)
          • 用JAVASCRIPT写了个测试算法(其实也没什么算法).仅供参考而已. -leoxxll(leoxxll); 2006-4-21 {1760} (#2919123@0)
            本文发表在 rolia.net 枫下论坛<HTML>
            <head>
            <script lang="javascript">
            var strIndex = "";
            var strInput;
            var targetNumber;
            var strTemp = "";
            var nInd = 0;

            function getNextNumber(N, a, b, m){
            for(var i=m; i<=N-(b-a+1); i++){
            strIndex += i;

            if(a==b){
            //Got the indexes
            document.getElementById("output").innerHTML += (strIndex + ": ");
            //insert '+' based on the indexes
            strTemp = strInput;
            for(var j=strIndex.length-1; j>=0; j--){
            nInd = parseInt(strIndex.charAt(j));
            strTemp = strTemp.substr(0, nInd) + '+' + strTemp.substring(nInd, strTemp.length);
            }
            document.getElementById("output").innerHTML += (strTemp + "<BR>");

            //
            if (eval(strTemp) == targetNumber) alert("Got it! " + strTemp + "=" + targetNumber + "\nResult: " + b);

            strIndex = strIndex.substr(0, strIndex.length-1);
            }else if(a<b){
            getNextNumber(N, a+1, b, i+1);
            }
            }

            strIndex = strIndex.substr(0, a-2);
            }

            function test(){
            document.getElementById("output").innerHTML ="";

            strInput = document.getElementById('txtString').value;
            targetNumber = parseInt(document.getElementById('txtNumber').value);

            for (var k=1; k<strInput.length; k++){
            getNextNumber(strInput.length, 1, k, 1);
            }
            }
            </script>
            </head>

            <body>
            <form>
            <table>
            <tr>
            <td>Digit String:<input type=text name=txtString id=txtString size=20></td>
            <td>Target Number:<input type=text name=txtNumber id=txtNumber size=20></td>
            </tr>
            <tr>
            <td>&nbsp;</td>
            <td><input type=button name=btnTest value=" Do It " onclick="test();"></td>
            </tr>
            <tr>
            <td colspan=10><div id=output style="width:200px; height:200px; overflow:auto"></div></td>
            </tr>
            </table>
            </form>
            </body>

            </HTML>更多精彩文章及讨论，请光临枫下论坛 rolia.net
            • 有个BUG: 056 会被认为是8进制, 仅供参考而已,所以凑和看吧..:) -leoxxll(leoxxll); 2006-4-21 (#2919271@0)
    • 老师教导过，不CARE COMPLEXITY 叫办法，不叫算法。 -yuanzidan(原子弹); 2006-4-21 (#2919144@0)
    • 不考虑算法用递归没多少行 -baalinca(scarb); 2006-4-21 (#2919360@0)
    • TopCoder has this kind of algorithm competitions. You can go there to practise. -benbenli(大岭); 2006-4-21 (#2920039@0)

More Topics

  • 老程序员第一次用copilot的一点点体会
  • 现在社区游泳池招救生员巡逻，过一会还要不停的点人头，这工作是否很快就被AI代替了，装一个摄像头后面是AI处理系统，这样只招一个等着救人就行了，人头沉下水一定时间立马强光照射，还可以分析水下人的状况来判断是否溺水等
  • 新冠疫苗引发心肌炎? 最新研究这样看
  • 这道几何题有解吗?
  • SAM 2 Demo
    • 枫下论坛主坛 /  工作学习 /  专业技术讨论