博文
开天窗程序(2006-07-27 17:29:00)
摘要：
开天窗(枚举+贪心):
大家的电子辞典应该都有开天窗这样的游戏吧。
现在我们就来讨论一下开天窗的程序。
题目：
Extended Lights Out (zoj 1354)
问题描述：
有一个5行6列的按钮阵列，每个按钮有一盏灯，当它被按下，它和它相邻四个(上下左右)的灯状态改变一次(亮->灭 或灭->亮)。
现在给出了这个阵列的初始亮灭状态，找一种操作让灯全灭。
问题分析：
v 显然按键是顺序无关的，而且最多按一次(按两次等于不按)。
v 最直接的想法：30个按键，每个有两种操作选择，总共要枚举2^30 ＝1073741824种方案。有点时间复杂度概念的人应该都知道这个方法不行……
v 要想使每一行的灯全灭掉，大家想一下，若第一行的灯的状态告诉你了，你怎样让这第一行灯全灭掉？(只要求这一行)。直观地看，把它的第一行的亮灯下面的开关按一下，上面就应该灭了，这样，把第一行的每个亮灯下面的第二行开关按一下，就可以把第一行亮灯全部干掉……
v 远点看，如果你的第二行开关没有全部干掉第一行的灯，第3,4,5行的开关根本对第一行不起作用，你第一行的灯永远也不会全灭……
v 假设你已经搞定第一行了，可第二行不一定全灭，于是要对第三行的开关操作。
v 后面各行的开关操作都受上一行约束……
v 各行操作完后，上面N-1行的灯应该全灭了，判断最后一行是否全灭，如是则就搞定这题了，否则要考虑改变第一行的开关状态继续往下这样……因为只有第一行不受别行约束……
问题的解决：
v 毫无疑问，搜索之。第1行有6个格，每格点或不点，共2^6＝64种状态。
v ......
简单机器人模拟(2006-07-27 17:20:00)
摘要：
简单机器人模拟
题目：(zju1708: Robot Motion)
以矩阵形式给定一张地图和机器人的初始位置。矩阵上每一点的字母代表在这一点机器人的移动方向。如果机器人按图中信息能走出的话输出需要的步数。如果机器人进入某个循环则输出循环前所走的步数和循环的长度。
v Sample Input
v 3 6 5 //地图行列大小和机器人起始点
NEESWE //ＮＥＳＷ分别表示North,East,South,West四个方向
WWWESS
SNWWWW
4 5 1 //另一个TEST
SESWE
EESNW
NWEEN
EWSEN
0 0 0 //000结束输入
v Sample Output
10 step(s) to exit
3 step(s) before a loop of 8 step(s)
源程序如下：
#include<iostream>
using namespace std;
int data[100][100];
int row,col; //地图行列数
void move(int r,int c)
{
int step=1; //记录每个坐标的步数信息(开始是第一步)
bool Noexit=true; //是否已经出界状态(开始肯定没出界^_^)
while(Noexit&&data[r][c]<0) //要判断是否出界还要......
程序设计基本知识结构(2006-07-27 17:08:00)
摘要：基本知识结构:
• 编码
• 文件输入/输出
• 大文件的问题
• 行超长的问题
• 数学运算
• 字符串处理
• 表达式求值/展开
• 英文数字朗读
• 简单程序的模拟执行(文法识别)
• 递归
• 数据结构
• 表示
• 线性结构
• 树: 边列表, 父亲, 遍历结果, “括号表示”
• A(B(H(), I(), J()), C(D(), E(F(), G())))
• 图
• 线性结构基本算法
• 排序
•&n......
一个简单的贪心算法(买牛奶)(2006-07-27 16:53:00)
摘要：
简单的贪心算法
题目：Mixing Milk（usco76）
问题描述：
某商人欲从M个农民那里购买N公斤牛奶。给定整数M，N及若干个农民拥有牛奶的价格和总量。问他最少需要多少钱可以购买N公斤牛奶
v Sample Input:
100 5 //商人要买的牛奶量和总共有的农民数(N,M)
5 20 //以下５行，是每个农民的牛奶单价和他有的牛奶总量
9 40
3 10
8 80
6 30
v Output:
630 //花的最少钱
用贪心法的关键是找到最优的度量标准。既然本题要求花钱最小，我们就可以选择牛奶的价格为度量标准。这是个简单的贪心算法：商人想花最少钱买牛奶，肯定是先挑便宜的买，把最便宜的买光了，还不够量的话，就去买次便宜的……直到数量够了为止。
源程序如下：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct intpair
{
intpair(int a=0,int b=0)
{
price=a;
num=b;
}//intpair
int price,num;//价格和数量
} ;
bool small(intpair v1,intpair v2)//为sort写的小函数
{
return v1.price<v2.price;
}//......