`
sunlujing
  • 浏览: 179829 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

编程之美 烙饼问题 java实现(检测状态是否出现过)

阅读更多

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语言:烙饼排序算法与买书问题源码》 在计算机科学的世界里,算法是解决问题的关键。本文将深入探讨两个编程问题:烙饼排序算法和买书问题,这两个问题都涉及到C语言的高效实现。我们将通过源代码分析...

    《烙饼问题》课件.ppt

    烙饼问题的数学应用 《烙饼问题》课件.ppt是一个关于数学应用的教学资源,旨在让学生通过探索和分析烙饼问题,学习数学知识,发展逻辑思维和解决问题的能力。下面是该资源的知识点总结: 一、数学概念: 1. 最...

    数学广角优化烙饼问题PPT课件.pptx

    《数学广角优化烙饼问题》是一份针对中小学生设计的专业课件,主要讲解如何通过优化策略来解决实际生活中的烙饼问题,旨在培养学生的逻辑思维和优化意识。在这个问题中,核心是找到烙饼最节省时间的方法。 首先,...

    烙饼问题.ppt

    烙饼问题与时间复杂度分析 在这个文件中,我们可以看到一个经典的烙饼问题,它是计算机科学中一个著名的例子,用于说明时间复杂度的概念。下面我们将详细解释这个问题的解决方案和相关的知识点。 首先,让我们了解...

    82烙饼问题.ppt

    • 我们掌握了优化烙饼问题的解决策略,包括通过分析烙饼次数与所需时间之间的关系,实现节约时间和能源。 • 我们可以将优化烙饼问题的思想应用于其他领域,例如电脑小游戏等。 • 我们可以通过这种思想,解决...

    烙饼问题 (4).ppt

    "烙饼问题",也被称为"煎饼问题"或"三明治问题",是计算机科学中的一个经典问题,属于算法优化的范畴。这个问题源于生活中的实际情况:在平底锅中,每次只能同时烙两张饼,饼需要烙两面,每面需要相同的时间。其目标...

    华为oj烙饼排序

    【华为OJ烙饼排序】是华为在线测评平台(OpenJudge)上的一道高级编程题目,主要考察的是排序算法的应用和实现。烙饼排序(Flipping Sorting),也称为煎饼排序,是一种基于比较的排序算法,它的灵感来源于煎饼翻转...

    烙饼问题教学设计.doc

    烙饼问题是一种经典的数学问题,主要涉及如何在有限的时间和资源下,通过优化策略实现效率最大化。在这个教学设计中,教师江海峰针对四年级学生,依据九年义务教育新课标(人教版)数学教材第七册的相应内容,旨在让...

    烙饼问题教学设计及反思.doc

    《烙饼问题》的教学设计与反思主要关注如何利用数学优化思想解决实际问题,特别是通过解决烙饼的问题,培养学生的逻辑思维能力和解决问题的能力。本教学活动旨在让学生体验运筹学的概念,理解优化思想,并掌握寻找...

    烙饼问题(1).ppt

    《烙饼问题》是数学中的一个经典问题,它属于优化问题的一个范畴,旨在寻找最有效率的方法来完成特定任务。在这个问题中,我们探讨的是如何在最短的时间内烙制一定数量的饼,同时充分利用煎饼锅的烹饪能力。下面我们...

    《烙饼问题》教学课例11.doc

    《烙饼问题》的教学课例主要探讨的是如何运用优化思维解决实际问题,特别是通过烙饼这一日常生活中的例子,让学生理解并初步体验运筹思想和对策方法。运筹思想是一种数学策略,它涉及到在多种可能的解决方案中寻找...

    烙饼问题11-2.ppt

    《烙饼问题11-2.ppt》是一个探讨优化算法的经典问题,主要涉及数学和计算机科学中的调度理论。这个问题的核心是找到在有限资源下完成任务的最有效策略,特别是当资源(在这里是平底锅)只能处理有限数量的任务时。在...

    四年级数学上册烙饼问题.pptx

    这篇PPT主要探讨了在数学问题中如何有效地利用时间和资源,特别关注了“烙饼问题”。烙饼问题是一个经典的优化问题,它源自于日常生活中的烹饪活动,旨在寻找最小化完成任务所需时间的方法。在这个问题中,每次只能...

    数学广角—烙饼问题教学设计.doc

    【数学广角—烙饼问题】是小学四年级数学课程中的一个重要知识点,主要涉及的是优化问题,即如何在有限条件下以最有效的方式解决问题。在这个教学设计中,教师以烙饼的过程为例,引导学生探讨如何合理安排操作以节省...

    《烙饼问题》 (3).ppt

    《烙饼问题》是小学数学中的一个重要概念,它属于运筹学的范畴,旨在通过合理的规划和安排,达到最优化的时间利用。这个问题的核心是解决在有限的资源和条件下,如何高效地完成一系列任务。 首先,我们要理解烙饼...

    经典算法,当然是经典了

    烙饼问题展示了如何在有限的操作下达到目标状态,它与计算机科学中的数据结构和排序算法有着紧密联系。 另一个标签“金刚坐飞机”可能是指优先级队列问题,或者更具体地说,是“大亨上飞机”问题。这个问题模拟了...

    四年级数学烙饼问题教学设计.doc

    1. **统筹思想**:在烙饼问题的教学中,统筹思想是一个核心概念。它是指在处理问题时,通过合理规划和安排,以达到最高效、最节省资源的结果。在这个问题中,学生需要理解如何在有限的条件下(每次只能烙两张饼)...

    《数学广角合理烙饼问题》课件.ppt

    《数学广角合理烙饼问题》是一门课程,旨在教授如何高效解决数学中的优化问题,特别是涉及时间管理和资源利用的问题。在这个课件中,我们关注的是一个经典的数学问题,即如何在最少的时间内烙制一定数量的饼,每个饼...

Global site tag (gtag.js) - Google Analytics