import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
/**
* 对应编程之美的烙饼翻转
* @author sunlujing
*
*/
public class CookieReverse {
private int cookie_cnt =10;
private int[] cookies={3,2,1,6,5,4,9,8,7,0};
private int [] med_cookies_states= {3,2,1,6,5,4,9,8,7,0};
private int max_step = 2*(cookie_cnt);
private int[] switchStrategy = new int[max_step];
private int[] switchStrategy_res = new int[max_step];
private Map<String,Integer> searchStates = new HashMap<String,Integer>();
public int lowerbound(int [] med_cookies_states){
int res=0;
for(int i=1;i< cookie_cnt;i++){
if(Math.abs(med_cookies_states[i]-med_cookies_states[i-1])!=1){
res++;
}
}
return res;
}
/**
* 记录状态是否搜索过
* 使用hashMap来作为state的key值,value 为该状态下所经历的step
* 如果当前状态的step值比hashmap中的小,则不需要剪掉这个分支
* @param med_cookies_states
* @param step
* @return
*/
public boolean isUnSearch(int [] med_cookies_states,int step){
String temp="";
for(int i=0;i< cookie_cnt;i++){
temp+=String.valueOf(med_cookies_states[i]);
}
if(searchStates.get(temp)==null){
searchStates.put(temp, step);
return true;
}else{
if(searchStates.get(temp) >step){
searchStates.put(temp, step);
return true;
}else{
return false;
}
}
}
public boolean isSorted(int [] med_cookies_states){
for(int i=1;i< cookie_cnt;i++){
if(med_cookies_states[i-1] > med_cookies_states[i]){
return false;
}
}
return true;
}
public void reverse(int begin,int end){
int i,j,t;
for(i=begin,j=end;i<j;i++,j--){
t = med_cookies_states[i];
med_cookies_states[i] = med_cookies_states[j];
med_cookies_states[j] =t ;
}
}
public void showStrategy(){
for(int i=0;i<max_step;i++){
System.out.print(switchStrategy_res[i]+" ");
}
}
public void search(int step){
int lowerBound = lowerbound(med_cookies_states);
if(lowerBound+step >= max_step){
return ;
}
if(!isUnSearch(med_cookies_states,step)){return;}
if(isSorted(med_cookies_states)){
if(step < max_step){
max_step = step;
for(int i=0;i<max_step;i++){
switchStrategy_res[i]=switchStrategy[i];
}
}
return;
}
for(int i=1; i < cookie_cnt;i++){
reverse(0,i);
switchStrategy[step]=i;
search(step+1);
reverse(0,i);
}
}
public static void main(String[] args) {
CookieReverse ins = new CookieReverse();
ins.search(0);
System.out.println(ins.max_step);
ins.showStrategy();
}
}
相关推荐
翻转烙饼排序问题是一种经典的计算机科学问题,其核心是在一系列烙饼中通过翻转操作将烙饼按大小顺序排列。这个问题在计算机科学领域中,尤其是算法设计与分析、数据结构以及人工智能等领域有着广泛的应用。下面,...
《程序之美-C语言:烙饼排序算法与买书问题源码》 在计算机科学的世界里,算法是解决问题的关键。本文将深入探讨两个编程问题:烙饼排序算法和买书问题,这两个问题都涉及到C语言的高效实现。我们将通过源代码分析...
在数学教育领域,将实际问题抽象化并以此作为教学案例是常见的教学方法之一。《烙饼问题》正是这样一个将实际生活中的烙饼操作转化为数学问题的案例,它不仅能够让学生在解决实际问题的过程中掌握数学知识,还能够...
今天我们要探讨的是一个既亲切又富有挑战性的数学问题——烙饼问题,以及如何利用优化策略来找到解决这一问题的最节省时间的方法。 《数学广角优化烙饼问题》这份课件,旨在通过一系列精心设计的数学活动,培养中...
烙饼问题与时间复杂度分析 在这个文件中,我们可以看到一个经典的烙饼问题,它是计算机科学中一个著名的例子,用于说明时间复杂度的概念。下面我们将详细解释这个问题的解决方案和相关的知识点。 首先,让我们了解...
• 我们掌握了优化烙饼问题的解决策略,包括通过分析烙饼次数与所需时间之间的关系,实现节约时间和能源。 • 我们可以将优化烙饼问题的思想应用于其他领域,例如电脑小游戏等。 • 我们可以通过这种思想,解决...
"烙饼问题",也被称为"煎饼问题"或"三明治问题",是计算机科学中的一个经典问题,属于算法优化的范畴。这个问题源于生活中的实际情况:在平底锅中,每次只能同时烙两张饼,饼需要烙两面,每面需要相同的时间。其目标...
【华为OJ烙饼排序】是华为在线测评平台(OpenJudge)上的一道高级编程题目,主要考察的是排序算法的应用和实现。烙饼排序(Flipping Sorting),也称为煎饼排序,是一种基于比较的排序算法,它的灵感来源于煎饼翻转...
烙饼问题,尽管听起来并不起眼,实际上却是一个融合了数学理论与现实问题解决能力的经典教学案例。本文将详细探讨这一问题的教学设计,特别是针对四年级学生的教学计划,其目的是让学生掌握解决问题的最优方案,同时...
《烙饼问题》是数学中的一个经典问题,它属于优化问题的一个范畴,旨在寻找最有效率的方法来完成特定任务。在这个问题中,我们探讨的是如何在最短的时间内烙制一定数量的饼,同时充分利用煎饼锅的烹饪能力。下面我们...
《烙饼问题》的教学课例主要探讨的是如何运用优化思维解决实际问题,特别是通过烙饼这一日常生活中的例子,让学生理解并初步体验运筹思想和对策方法。运筹思想是一种数学策略,它涉及到在多种可能的解决方案中寻找...
《烙饼问题11-2.ppt》是一个探讨优化算法的经典问题,主要涉及数学和计算机科学中的调度理论。这个问题的核心是找到在有限资源下完成任务的最有效策略,特别是当资源(在这里是平底锅)只能处理有限数量的任务时。在...
随着问题的逐步深入,学生需要考虑如何高效安排烙饼的顺序,以实现时间上的最优化。通过实际操作和计算,学生们很快就发现,一次性烙两个饼显然比烙一个饼更为高效。此外,教师还鼓励学生通过小组合作和交流,探讨烙...
这篇PPT主要探讨了在数学问题中如何有效地利用时间和资源,特别关注了“烙饼问题”。烙饼问题是一个经典的优化问题,它源自于日常生活中的烹饪活动,旨在寻找最小化完成任务所需时间的方法。在这个问题中,每次只能...
它通过将日常生活中烙饼的过程转化为数学模型,让学生在解决实际问题的过程中,体会到数学之美和实用性。 “合理烙饼问题”指的是在有限的资源下,如何在最短的时间内烙制出最多的饼。这个问题虽然简单,却能巧妙地...
【数学广角—烙饼问题】是小学四年级数学课程中的一个重要知识点,主要涉及的是优化问题,即如何在有限条件下以最有效的方式解决问题。在这个教学设计中,教师以烙饼的过程为例,引导学生探讨如何合理安排操作以节省...
在烙饼问题中,每个饼都需要两面都烙过才算完成,而我们的锅一次只能放下两张饼。每面的烙制时间是固定的3分钟,这就意味着,无论是烙制一张饼还是两张饼,完成它们都需要6分钟。 针对烙制3张饼的情况,我们可以...
《烙饼问题》是小学数学中的一个重要概念,它属于运筹学的范畴,旨在通过合理的规划和安排,达到最优化的时间利用。这个问题的核心是解决在有限的资源和条件下,如何高效地完成一系列任务。 首先,我们要理解烙饼...
烙饼问题展示了如何在有限的操作下达到目标状态,它与计算机科学中的数据结构和排序算法有着紧密联系。 另一个标签“金刚坐飞机”可能是指优先级队列问题,或者更具体地说,是“大亨上飞机”问题。这个问题模拟了...