算法分析设计与实践 实验一

swust oj 254

题目描述
麦兜最喜欢的食物是煎饼，每次在街上看到煎饼摊的时候都会在那里停留几分钟。最吸引麦兜还是煎饼师傅那一手熟练的翻煎饼的技术，一堆煎饼在那里，师傅只需要用铲子翻几下，就让煎饼整齐的叠在了一起。 这天，为了庆祝麦兜被保送上研究生，他从煎饼师傅那里买回来一些煎饼请客。但是麦兜买回的煎饼大小不一，麦兜太想吃煎饼了，他想吃这些煎饼中最大的那个。麦兜还知道同学们也很喜欢煎饼，为了表示他的诚意，他想让同学们先吃，麦兜最后吃，因此，麦兜想把煎饼按照从小到大的顺序叠放在一起，大的在最下面。这样麦兜就可以在最后拿到最大的那一块煎饼了。 现在请你帮助麦兜用煎饼师傅翻煎饼的方法把麦兜买的煎饼从小到大的叠在一起。煎饼师傅的方法是用铲子插入两块煎饼之间，然后将铲子上的煎饼翻一转，这样铲子上第一个煎饼就被翻到了顶上，而原来顶上的煎饼则被翻到了刚才插入铲子的地方。麦兜希望这样翻煎饼的次数最少。
输入:输入包括两行，第一行是一个整数n(1<=n<=1000)，表示煎饼的个数，接下来的一行有n个不相同的整数，整数间用空格隔开，每个整数表示煎饼的大小（直径），左边表示顶部，右边表示底部。
输出:输出为一行，翻煎饼的最少次数
样例输入：

 5
 5 4 2 3 1

样例输出:

4

分析

题意：

其实这道题理解题意后就很容易上手，煎饼师傅将铲子插入俩个饼之间，然后最上面的饼就被翻到了插入铲子的下面而铲子上的第一个被翻到了顶上，麦兜要找到翻煎饼的次数最少，其实就是先找到第一个最大的煎饼，然后判断它是不是在正确位置，不是就判断它是不是在顶上，不在就翻到顶上然后翻到顶上，在就直接翻到最后，接着找第二个最大的煎饼，按照第一个煎饼的思路进行，最后放到倒数第二个位置，接着第三个一直到第n个煎饼，用一个numb变量计数，其实就是减治法的思路，把规模为n的问题化为规模为n-1的问题：例如：

numb=1    煎饼顺序变为1 3 2 4 5
numb=2    煎饼顺序变为3 1 2 4 5
numb=3    煎饼顺序变为2 1 3 4 5
numb=4    煎饼顺序变为1 2 3 4 5

c++代码

#include<iostream>
#include<algorithm>
#define  M  1000
using namespace std;
int main()
{
	int numb = 0;
	int a[M];
	int n;
	cin >> n;//煎饼个数 
	for (int i = 1; i <= n; i++)
		cin >> a[i]; //输入煎饼大小
	for (int i = 1; i <= n; i++)
	{
		int max = 1;
		//找到每次最大煎饼数组的下标
		for (int j = 1; j <= n - i + 1; j++) //注意每次最大煎饼放的位置不同
		{
			if (a[j] > a[max])
			{
				max = j;
			}
		}
		if (max != n - i + 1) {
			//判断煎饼是否在正确位置
			if (max != 1)    //不在最上面 
			{
				for (int k = 1; k <= max / 2; k++)
				{
					swap(a[k], a[max - k + 1]);
				}
				numb++;
			}
			//在最上面  翻转到合适的位置
			for (int k = 1; k <= (n - i + 1) / 2; k++)
			{
				swap(a[k], a[n - i - k + 2]);
			}

			numb++;
		}
	}
	cout << numb << endl;
}

swust oj 480

题目描述
There are n lockers in a hallway numbered sequentially from 1 to n. Initially, all the locker doors are closed. You make n passes by the lockers, each time starting with locker #1. On the ith pass, i = 1, 2, ..., n, you toggle the door of every ith locker: if the door is closed, you open it, if it is open, you close it. For example, after the first pass every door is open; on the second pass you only toggle the even-numbered lockers (#2, #4, ...) so that after the second pass the even doors are closed and the odd ones are opened; the third time through you close the door of locker #3 (opened from the first pass), open the door of locker #6 (closed from the second pass), and so on. After the last pass, which locker doors are open and which are closed? How many of them are open? Your task is write a program to output How many doors are open after the last pass? Assumptions all doors are closed at first.
输入:
a positive numbers n, total doors. n<=100000
输出:
a positive numbers ，the total of doors opened after the last pass.
样例输入:
10
样例输出：
3

分析

其实这道题就是一道带锁的门的问题，在算法设计与分析基础上是经常讲的一个问题。
开始：所有的门全部关上的
第一次：所有门打开
第二次：偶数门关闭，奇数门打开
第三次：3的倍数包括3的门在第二次的基础上打开或者关闭
···
第n次：求最后一次过了，有多少个门是打开的？

思路：

这是一道模拟题，需要对数据的模拟，可以用循环做，但是n比较大，二重循环从1遍历一般都会超时，我第一次是用c++ STL的map来做的，答案是正确的，但是提交超时了，这个我就搞不懂了，后来又用数组来做，结果还是超时，后来通过模拟数据，你会发现一个规律：

这个规律就是打开的门=根号n的取整
即打开的门=(int)sqrt(n);
这就变得非常简单了

c++代码

#include<iostream>
#include<cmath>
using namespace std;
int main()
{
	int n;
	cin>>n;
	cout<<(int)sqrt(n)<<endl;
}

swust oj 536

题目：
The problem is named after Flavius Josephus, a Jewish historian who participated in and chronicled the Jewish revolt of 66-70C.E. against the Romans. Josephus, as a general, managed to hold the fortress of Jotapata for 47days, but after the fall of the city he took refuge with 40 diehards in a nearby cave. There the rebels voted to perish rather than surrender. Josephus proposed that each man in turn should dispatch his neighbor, the order to be determined by casting lots. Josephus contrived to draw the last lot, and as one of the two surviving men in the cave, he prevailed upon his intended victim to surrender to the Romans. Your task:computint the position of the survivor when there are initially n people.
输入：
a Positive Integer n is initially people. n< = 50000
输出：
the position of the survivor
样例输入：
6
样例输出：
5

分析

我的想法：约瑟夫问题我一看到就想到的单循环链表，其实这道题还没有数据结构的中文（约瑟夫问题的实现）难，用链表做非常简单，循环至最后一个节点的条件就是：s->next!=s

c++代码

#include<iostream>
using namespace std;
typedef struct node//定义
{
	int data;
	struct node *next;
}linknode;
void createlist(linknode *&L)//创建单循环链表
{
	int n;
	cin>>n;
	linknode *r,*s;
	L=new(linknode);
	r=L;
	for(int i=1;i<=n;i++)
	{
		s=new(linknode);
		s->data=i;
		r->next=s;
		r=s;
	}
	r->next=L->next;
	s=L->next;
	while(s->next!=s)
	{
		s->next=s->next->next;
		s=s->next;
	}
	cout<<s->data<<endl;
}
int main()
{
	linknode *L;
	createlist(L);
	
}

swust 348

这道题我明天再写，稍微有点难，思路不清晰的话没法做
思路：这道题我想的是用到了DFS（深度优先搜索），用递归实现DFS，这道题其实思路比较好理解，在规定的时间内，先找到最大的花生，然后找剩下的最大的花生，直到时间结束，其实这道题还有一个问题就是这种解看似是多多最多可以采到的花生，其实在规定的时间内存在着花生少但是路径短的几组花生采到的可能比找路径长的花生多的要多，应该要用到动态规划，这个就按照这个思路用DFS做，就能解出答案。
更新：数字三角模型优化

swust 642

俄式乘法，用递归做，用数组存奇数产生的m,用变量numb=0计数，这里一定要用引用回传参数numb
C++代码如下：

#include<iostream>
#define M 1000
using namespace std;
int CR(int n,int m,int &numb,int a[])
{
	if(n==1)
	{
		return m;
	}
	else if(n%2==0)
	{
		return CR(n/2,2*m,numb,a);
	}
	else if(n%2!=0)
	{
		a[numb]=m;
		numb++;
		return CR((n-1)/2,2*m,numb,a);
	}
}
int main()
{ 
    int sum=0;
    int x;
    int a[M]={0};
	int numb=0;
	int n,m;
	cin>>n>>m;
    x=CR(n,m,numb,a);
    for(int i=0;i<numb;i++)
    {
    	cout<<a[i]<<" "<<"+"<<" ";
    	sum+=a[i];
    }
    cout<<x<<" "<<"=";
    sum+=x;
    cout<<" "<<sum<<endl;
}