美文网首页
2019-07-10 数据结构和算法（妙味杜鹏）

2019-07-10 数据结构和算法（妙味杜鹏）

作者: DreamNeverDie | 来源:发表于2019-07-10 22:01 被阅读0次

八皇后


<!DOCTYPE HTML>
<html>

<head>
    <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
    <title>无标题文档</title>
    <style>
        * {
            margin: 0;
            padding: 0;
        }

        li {
            list-style: none;
        }

        #ul1 {
            height: auto;
            margin: 20px auto;
            overflow: hidden;
            border: 1px #ccc solid;
            border-right: none;
            border-bottom: none;
        }

        #ul1 li {
            float: left;
            border: 1px #ccc solid;
            border-left: none;
            border-top: none;
            background-size: cover;
        }

        #ul1 li.active {
            animation: .5s infinite linear flash;
            -webkit-animation: .5s infinite linear flash;
        }

        @keyframes flash {
            0% {
                opacity: 0.1;
            }

            50% {
                opacity: 1;
            }

            100% {
                opacity: 0.1;
            }
        }

        @-webkit-keyframes flash {
            0% {
                opacity: 0.1;
            }

            50% {
                opacity: 1;
            }

            100% {
                opacity: 0.1;
            }
        }
    </style>
</head>

<body>
    <ul id="ul1">
    </ul>
    <script>

        var oUl = document.getElementById('ul1');
        var aLi = oUl.getElementsByTagName('li');
        var sizeGird = 50;
        var num = 8;
        var iCount = 0;
        var posArr = [];
        var posArrAll = [];
        var arrColor = ["red", "blue", "yellow", "pink", 
                                        "orange", "black", "green", "purple"]
        init();

        function init() {
            createGird();
            setQueen(0);
            //console.log( posArrAll );
            showImg();
        }

        function createGird() {
            var len = num * num;

            oUl.style.width = num * (sizeGird + 1) + 'px';

            for (var i = 0; i < len; i++) {
                var oLi = document.createElement('li');
                oLi.style.width = sizeGird + 'px';
                oLi.style.height = sizeGird + 'px';
                oLi.index = -1;
                //oLi.innerHTML = oLi.index;
                oUl.appendChild(oLi);
            }

            for (var i = 0; i < num; i++) {
                for (var j = 0; j < num; j++) {
                    //i j num
                    aLi[i * num + j].x = j;
                    aLi[i * num + j].y = i;
                    //aLi[ i*num + j ].innerHTML = j + ',' + i;
                }
            }
        }

        function setQueen(iQueen) {

            if (iQueen == num) {
                posArrAll.push(posArr.concat());
                iCount++;
                return;
            }

            for (var i = 0; i < num; i++) {

                if (aLi[iQueen * num + i].index == -1) {
                    aLi[iQueen * num + i].index = iQueen;
                    //aLi[ iQueen*num + i ].innerHTML = iQueen;
                    posArr.push(aLi[iQueen * num + i]);
                    var x = aLi[iQueen * num + i].x;
                    var y = aLi[iQueen * num + i].y;

                    for (var j = 0; j < aLi.length; j++) {
                        if (aLi[j].index == -1 &&
                            (aLi[j].x == x || aLi[j].y == y ||
                             aLi[j].x - aLi[j].y == x - y ||
                             aLi[j].x + aLi[j].y == x + y))
                         {
                            aLi[j].index = iQueen;
                            //aLi[j].innerHTML = iQueen;
                        }
                    }

                    setQueen(iQueen + 1);

                    //回溯
                    posArr.pop();
                    for (var j = 0; j < aLi.length; j++) {
                        if (aLi[j].index == iQueen) {
                            aLi[j].index = -1;
                        }
                    }

                }
            }
        }

    function showImg() {

        change();
        setInterval(change, 2000);

              function change() {

            for (var i = 0; i < aLi.length; i++) {
                aLi[i].style.background = '';
                aLi[i].className = '';
            }

            var randomLi = posArrAll[Math.floor(posArrAll.length * Math.random())];

            for (var i = 0; i < randomLi.length; i++) {
             randomLi[i].style.background = arrColor[Math.floor(Math.random() * 8)]
             randomLi[i].className = 'active';
             randomLi[i].style.animationDelay = -Math.random() * 2 + 's';
             randomLi[i].style.webkitAnimationDelay = -Math.random() * 2 + 's';
            }

        }

    }

        </script>
        </body>
        </html>

A *寻路


<!DOCTYPE HTML>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<title>无标题文档</title>
<style>
*{ margin:0; padding:0;}
li{ list-style:none;}
#ul1{ height:auto; overflow:hidden; margin:20px auto; 
border:1px #000 solid; border-bottom:none; border-right:none;}
#ul1 li{border:1px #000 solid; border-top:none; border-left:none; float:left;}
#ul1 li.sty1{ background:red;}
#ul1 li.sty2{ background:green;}
#ul1 li.sty3{ background:blue;}
#input1{ width:100px; position:absolute; left:50%; margin-left:-50px;}
</style>
</head>

<body>
<ul id="ul1">
</ul>
<input type="button" value="开始寻路" id="input1">
<script>

var oUl = document.getElementById('ul1');
var aLi = oUl.getElementsByTagName('li');
var oInput = document.getElementById('input1');
var beginLi = oUl.getElementsByClassName('sty1');
var endLi = oUl.getElementsByClassName('sty2');

var map = [
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,3,3,3,3,3,3,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,
    0,0,0,0,1,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,2,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,3,3,3,3,3,3,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
];

var cols = Math.sqrt(map.length);
var sizeGird = 20;
var openArr = [];
var closeArr = [];

init();

function init(){
    createMap();
    oInput.onclick = function(){
        openFn();
    };
}

function createMap(){
    
    oUl.style.width = cols * (sizeGird + 1) + 'px';
    
    for(var i=0;i<map.length;i++){
        var oLi = document.createElement('li');
        oLi.style.width = sizeGird + 'px';
        oLi.style.height = sizeGird + 'px';
        oUl.appendChild(oLi);
        
        if( map[i] == 1 ){
            oLi.className = 'sty1';
            openArr.push(oLi);
        }
        else if(map[i] == 2){
            oLi.className = 'sty2';
        }
        else if(map[i] == 3){
            oLi.className = 'sty3';
            closeArr.push(oLi);
        }
        
    }
}

function openFn(){
    
    var nowLi = openArr.shift();
    
    if( nowLi == endLi[0] ){
        showLine();
        return;
    }
    
    closeFn(nowLi);
    
    findLi(nowLi);
    
    //console.log( openArr );
    
    openArr.sort(function(li1,li2){
        return li1.num - li2.num;
    });
    
    //console.log( openArr );
    
    openFn();
    
}
function closeFn(nowLi){
    closeArr.push( nowLi );
}

function findLi(nowLi){
    var result = [];
    for(var i=0;i<aLi.length;i++){
        if( filter(aLi[i]) ){
            result.push( aLi[i] );
        }
    }
    function filter(li){
        for(var i=0;i<closeArr.length;i++){
            if( closeArr[i] == li ){
                return false;
            }
        }
        for(var i=0;i<openArr.length;i++){
            if( openArr[i] == li ){
                return false;
            }
        }
        return true;
    }
    
    for(var i=0;i<result.length;i++){
        if( (Math.abs(nowLi.offsetLeft - result[i].offsetLeft)<= sizeGird + 1)
 && (Math.abs(nowLi.offsetTop - result[i].offsetTop)<= sizeGird + 1) ){
            result[i].num = f(result[i]);
            result[i].parent = nowLi;
            openArr.push( result[i] );
        }
    }
    
}

function showLine(){
    var result = [];
    var lastLi = closeArr.pop();
    var iNow = 0;
    findParent(lastLi);
    function findParent(li){
        result.unshift(li);
        if( li.parent == beginLi[0] ){
            return;
        }
        findParent(li.parent);
    }
    
    var timer = setInterval(function(){
        
        result[iNow].style.background = 'red';
        iNow++;
        if(iNow == result.length){
            clearInterval(timer);
        }
    },500);
    
}

function f(nodeLi){
    return g(nodeLi) + h(nodeLi);
}
function g(nodeLi){
    var a = beginLi[0].offsetLeft - nodeLi.offsetLeft;
    var b = beginLi[0].offsetTop - nodeLi.offsetTop;
    return Math.sqrt(a*a + b*b);
}
function h(nodeLi){
    var a = endLi[0].offsetLeft - nodeLi.offsetLeft;
    var b = endLi[0].offsetTop - nodeLi.offsetTop;
    return Math.sqrt(a*a + b*b);
}

</script>
</body>
</html>

背包问题（动态规划方法）

<!DOCTYPE HTML>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<title>无标题文档</title>
<script>

var M = 5;
var W = 16;
var arrP = [4,5,10,11,13];
var arrW = [3,4,7,8,9];
//13 + 10 -> 23   第三件+第五件
//13 + 4 + 5 -> 22 第一件 + 第二件 + 第五件

function show(M,W,arrP,arrW){
    var result = [];
    for(var i=0;i<=M;i++){
        result[i] = [];
        for(var j=0;j<=W;j++){
            if(i==0){
                result[i][j] = 0;
            }
            else if( arrW[i-1] > j ){
                result[i][j] = result[i-1][j];
            }
            else{
                result[i][j] = Math.max(arrP[i-1] + result[i-1][j - arrW[i-1]] , result[i-1][j]);
            }
        }
    }
    //console.log(result);
    return result[i-1][j-1];
}
console.log( show(M,W,arrP,arrW) );

//var arrP = [4,5];
//var arrW = [3,4];
//var W = 16;   //0 0 0 0 .... 0
//var W = 16;   //0 0 0 4 4 4 ..... 4
//var W = 7;   //0 0 0 4 (5,4) 5 5 9 9 ..... 9
//var W = 16;     //0 0 0 4 5 5 5 (10,9) 10 10 14  15 15 15 19 19 19


</script>
</head>

<body>
</body>
</html>

背包问题（贪心算法）

<!DOCTYPE HTML>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<title>无标题文档</title>
<script>

/*var M = 5;
var W = 16;
var arrP = [4,5,10,11,13];
var arrW = [3,4,7,8,9];

function show(M,W,arrP,arrW){
    var wholeArr = [];
    var result = 0;
    for(var i=0;i<M;i++){
        wholeArr.push({ p : arrP[i] , w : arrW[i] , r : arrP[i]/arrW[i] });
    }
    //console.log(wholeArr);
    wholeArr.sort(function(obj1,obj2){
        return obj2.r - obj1.r;
    });
    console.log(wholeArr);
    for(var i=0;i<wholeArr.length;i++){
        if( wholeArr[i].w <= W ){
            result += wholeArr[i].p;
            W -= wholeArr[i].w;
        }
    }
    return result;
}
console.log( show(M,W,arrP,arrW) );*/

/*1.33
1.25
1.43
1.38
1.44*/



var M = 5;
var W = 16;
var arrP = [4,5,10,11,12];
var arrW = [3,4,7,8,9];

function show(M,W,arrP,arrW){
    var wholeArr = [];
    var result = 0;
    for(var i=0;i<M;i++){
        wholeArr.push({ p : arrP[i] , w : arrW[i] , r : arrP[i]/arrW[i] });
    }
    //console.log(wholeArr);
    wholeArr.sort(function(obj1,obj2){
        return obj2.r - obj1.r;
    });
    //console.log(wholeArr);
    for(var i=0;i<wholeArr.length;i++){
        if( wholeArr[i].w <= W ){
            result += wholeArr[i].p;
            W -= wholeArr[i].w;
        }
        else{
            result += W/wholeArr[i].w * wholeArr[i].p;
            break;
        }
    }
    
    return result.toFixed(2);
}
console.log( show(M,W,arrP,arrW) );
</script>
</head>

<body>
</body>
</html>

相关文章

网友评论

      本文标题：2019-07-10 数据结构和算法（妙味杜鹏）

      本文链接：https://www.haomeiwen.com/subject/ztakkctx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|2019-07-10 数据结构和算法（妙味杜鹏）|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！