看到一个翻硬币题目,想了半天,不得其解,遂搜之...
发现这个博文写了几种思路,惊叹此人算法如此之好!
此处把几种思路以Java实现,特此记录...
http://blog.csdn.net/jia_xiaoxin/archive/2008/08/30/2852389.aspx
题目:
一摞硬币共有m枚,每一枚都是正面朝上。取
下最上面的一枚硬币,将它翻面后放回原处。然后取下最上面的2枚硬币,将他们一起翻面后再放回原处。再取3枚,取4枚……直至m枚。然后再从这摞硬币最上
面的一枚开始,重复刚才的做法。这样一直做下去,直到这摞硬币中的每一枚又都是正面朝上为止。例如,m为1时,翻两次即可。m为2时,翻3次即可;m为3
时,翻9次即可;m为4时,翻11次即可;m为5时,翻24次即可;…;m为30时,翻899次即可;…
输 入:
仅有的一个数
字
是这摞硬币的枚数m,0<m<1000。
输 出:
为了使这摞硬币中的每一枚又都是正面朝上所必
需翻的次数。
某单
元
格
输入:
30
某单元格等于:
899
思路:不管硬币的次序,只是记住每次的翻转和交换,硬币的初
始状态都是TRUE,每个COIN经过多伦的翻转后都变回TRUE,那么就求出了解,这是最简单的思路。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class TurnCoin {
public static void turn(int m){
int turnTimes = 0;
boolean flag = false;
boolean[] coins = new boolean[m];
for(int i=0;i<m;i++){
coins[i] = true;
}
while(!flag){
for(int i=0;i<m;i++){
for(int j=0;j<(i+1)/2;j++){
boolean temp = coins[j];
coins[j] = !coins[i-j];
coins[i-j] = !temp;
}
if((i+1)%2 == 1){
coins[i/2] = !coins[i/2];
}
turnTimes = turnTimes + 1;
flag = true;
for(int n=0;n<m;n++){
if(coins[n] == false){
flag = false;
break;
}
}
if(flag){
break;
}
}
}
System.out.println(turnTimes);
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
turn(n);
}
}
待继....
分享到:
相关推荐
### JAVA编程实现硬币翻转问题 #### 问题描述 本题目主要探讨了一个有趣的数学问题:假设有n枚硬币初始状态全部为正面朝上,按照一定的规则进行翻转操作,最终能否使得所有硬币再次回到全部正面朝上的状态。具体...
硬币翻转ppt动画,正面的内容经过翻转显示背面的内容,硬币翻转配合目录切换ppt乐趣动画模板。
### 归纳算法程序设计(硬币翻转问题) #### 知识点解析 本篇文章将详细介绍一个关于归纳算法的经典示例——硬币翻转问题,并通过一段C语言代码进行实现。该问题不仅可以帮助理解归纳法的基本思想,还能够加深对...
2、有N个硬币(N为偶数)正面朝上排成一排,每次将N-1个硬币翻过来放在原位置,不断地重复上述过程,直到最后全部硬币翻成反面朝上为止。设计程序让计算机把翻币的最简过程以及翻币次数输出(用*表示正面,O表示反面...
在桌面上有一排硬币,共N枚,每一枚硬币...现在要把所有的硬币翻转成反面朝上,规则是每次可翻转任意N-1枚硬币(正面向上的被翻转为反面向上,反之亦然)。求一个最短的操作序列(将每次翻转N-1枚硬币成为一次操作)。
标题“翻转的硬币群”暗示我们正在讨论一种与计算机图形学相关的特效,特别是涉及到硬币的动画效果。在IT行业中,这种效果通常通过编程或使用特定的软件工具来实现,例如Adobe Flash,该软件广泛用于创建互动式网页...
c语言经典算法之归纳算法。翻硬币。 编译软件:DEV C++5.
本文将深入探讨如何实现“硬币翻转”效果的动画,这通常用于头像或其他图形元素,为用户界面增添动态感和互动性。 首先,Android提供了两种主要类型的动画:补间动画(Tween Animation)和帧动画(Frame Animation...
在这个问题中,递归可能会考虑每次翻转一个硬币或不翻,然后看哪种情况能更快地使所有硬币倒下。动态规划则是通过存储已经解决的子问题的结果,避免重复计算,提高效率。 在8枚硬币问题中,每个硬币有两种状态:...
采用一位数组的数据结构,代码精简,简单明了
该算法使用贪心法翻硬币
3. **回溯法**:对于更复杂的翻硬币问题,可能需要尝试不同的翻转组合,这时可以使用回溯法。从第一个硬币开始,尝试翻转或不翻转,然后递归地处理下一个硬币,直到达到目标状态或确定无法达到目标状态并回溯。 4. ...
蓝桥杯是一项旨在培养和选拔优秀计算机软件和信息技术专业人才的比赛,涵盖多种编程语言和难度级别,而“翻硬币”问题可能涉及到组合优化、动态规划或者图论等计算机科学的基础概念。 【标签】"c++ 蓝桥杯" 明确了...
在这个场景中,"C++中MFС实现画硬币"是一个具体的实例,它涉及到图形用户界面(GUI)的设计和绘图功能的实现。 首先,要实现画硬币的功能,我们需要理解MFC中的CView类。CView是MFC框架中负责视图绘制的主要类,它...
例如,如果硬币面额为1、3和4,目标金额为7,贪心策略会选取两个4元硬币和一个1元硬币,而实际最优解是两个3元硬币和一个1元硬币。 7. **扩展应用**:贪心算法在很多领域都有应用,如任务调度、背包问题、最小生成...
1. **事件处理**:JavaScript中的事件监听器可以捕捉用户的点击或触摸动作,当用户触发翻硬币的行为时,执行相应的翻转动画。 2. **CSS3变换**:CSS3的transform属性可以用于改变元素的位置、大小、形状等,翻硬币...
标题中的“5dbe1685a866_matlab图像分割_硬币_硬币识别_图像识别硬币_图像硬币_”表明这是一个关于使用MATLAB进行图像处理,特别是针对硬币识别的项目。描述提到的是一个完整的程序,能够检测图像中硬币的数量并确定...
在`硬币找钱.txt`和`简单的硬币找钱.txt`文件中,可能包含了具体的代码实现或不同版本的解法。 8. **复杂度分析**:动态规划解法的时间复杂度是`O(n * W)`,其中`n`是硬币种类数,`W`是最大金额。空间复杂度为`O(W)...
"Flip: 硬币翻转网络应用程序"是一款利用JavaScript技术构建的互动应用,它模拟了现实生活中硬币翻转的过程,并在网络环境中提供了一个趣味性的交互体验。在这款应用程序中,用户可以进行虚拟的硬币翻转,适用于游戏...
从名字可以推测,其中的“翻硬币”题目可能与概率论、策略规划或算法优化等计算机科学领域有关。在编程竞赛中,这类题目往往需要参赛者综合运用多种编程技巧和算法知识。 具体来讲,蓝桥杯VIP题和题解中的“VIP”...