网站logo设计免费版在线,软件技术买什么笔记本好,WordPress防伪证书插件,标书制作的六步骤源地址为#xff1a;http://bbs.csdn.net/topics/390854089 昨天晚上在CSDN论坛上看到这道题#xff0c;思索一番后想到一个解决方案#xff0c;也简单实现了。今天早上把博客补一补。算是做个笔记吧。 题目#xff1a; 有m个人面向南方站成一排(m ≥1)#xff0c;每喊一次… 源地址为http://bbs.csdn.net/topics/390854089 昨天晚上在CSDN论坛上看到这道题思索一番后想到一个解决方案也简单实现了。今天早上把博客补一补。算是做个笔记吧。 题目 有m个人面向南方站成一排(m ≥1)每喊一次口号可以有n个人同时转身一次(1≤n≤m)问共需喊多少次口号所有人最终全部面向北方请编写一个函数函数有两个参数分别为m和n函数返回值为最终需要的次数若经过无穷大次仍然无法全部转向北方则输出-1.例1m 6,n 5:用0表示面向南方1表示面向北方过程如下 0 0 0 0 0 0
0 1 1 1 1 1
1 1 0 0 0 0
0 0 0 1 1 1
1 1 1 1 0 0
0 0 0 0 0 1
1 1 1 1 1 1 返回6例2m 3,n 2:返回-1 关注这个帖子的人还蛮多的不少人都或完整或不完整的给出了自己的方案。这些方案集中在寻找这个问题的公式解。 在还没看下面的回答之前我思考了一下与大部分网友不同的是从一开始我就没想要找到这个问题的公式解。我发现这本质上是一个搜索问题。为什么这么说且看下面的分析。 1.这m个数其实没有位置之分m的数的状态可以用0和1的个数来标记。 2.一旦指定mm就不会再变化了所以甚至可以只用0的个数来标记状态在这里我用所有m个数的和来标记状态1的个数。 3.每一次变化n个数相当于向前搜索。用x表示0的个数用y表示1的个数。变化n个数对m个数和的影响就是加上一个数。这个数可能有多种可能取值的上限和0的个数有关下限和y的个数有关。用max和min来表示上限和下限具体来说当xn时max n当xn时max x - (n - x) 2x - n当yn时min -n当y n 时min n - 2y。 4.人工智能课上介绍的搜索算法有很多BFSDFSA-star之类的。BFS能够得到最优解但是时间、空间开销可能比较大DFS可能在短时间内找到解但不能保证是最优的A-star有很多优点解是最优的速度也快可是需要启发式函数。这里我采用BFS。 下面是我的代码 import java.util.ArrayList;
import java.util.Iterator;import javax.management.openmbean.ArrayType;
import javax.management.openmbean.SimpleType;public class OneAlgorithm {/*** * param x: x is number of zeros* param y: y is number of ones * return*/public static int max(int x, int y, int n){int max 0;if(x n)max n;elsemax 2 *x - n;return max;}public static int min(int x, int y, int n){int min 0;if(y n)min -n;elsemin n - 2*y;return min;}/*** * param m* param n* return*/public static int BFS(int m, int n){if(m % n 0)return n;ArrayListInteger states new ArrayListInteger();ArrayListInteger floors new ArrayListInteger();int floor 0;int zeros m;floors.add(floor);states.add(zeros);int index 0;int max, min;int x m;int y 0;max max(x,y,n);min min(x,y,n);while(true){while(max min){zeros x - min;if(zeros 0)return floors.get(index)1;if(floors.indexOf(index) floor)floor;if(!states.contains(x-min)){states.add(x-min);floors.add(floor); }min min 2;} index index 1;if(index1 states.size())return -1;x states.get(index);y m - x;max max(x,y,n);min min(x,y,n);}}public static void main(String[] args){int temp BFS(13,7);System.out.println(temp);}
} 转载于:https://www.cnblogs.com/moqiguzhu/p/3947984.html
