寒假打卡Day3

今天开始看的是 这本书???? d6tc

我就截取看到的重点做了些笔记 （绝对不是因为懒(/ω＼)）

算法的效率

复杂度

分为两方面：

• Time Complexity
• Space Complexity

在竞赛中，题目限制通常为 1s ，即大约10⁸ 次操作，因此我们通常遇到的都是时间复杂度过高的问题。

表示法：Big-Oh-Notation

诸如O(n),O(n²)···O(g(n))， g(n)可以认为是1s内的操作次数

e.g. 给出m个数a_i (i=1,2,···,m)，找出最大的n个数 ( n ≤ m )

• m ≤ 10⁶
• n ≤ 1,000
• 0 ≤ a_i ≤ 10⁶

解法一 n次搜索

1. 数据录入a[m]
2. 找出a中最大的，输出并剔除
   ……
   n. 找出a中最大的，输出

此算法复杂度为O(m × n)

解法二 排序

1. 录入a[m]
2. 降序排列
3. 输出前n个数

此算法复杂度为O(mlogm + n)

解法三 统计

1. 将p出现的次数计入c[p]
2. 从最大的p开始向下，按c[p]记录的次数输出p，输出累计n次

此算法复杂度为O(m + n + max(a_i))

复杂度比较

由表知：O(n),O(logn),O(√n),O(nlogn)属于高效率算法；而O(n²),O(2ⁿ),O(n!)属于缺乏技巧的强行计算算法。不过问题不绝对，处理数据相对允许的情况下，暴力方法有时更加省力，每道题都用技巧那可真的是大佬了????

Problem：Maximum Profit????

You can obtain profits from foreign exchange margin transactions. For example, if you buy 1000 dollar at a rate of 100 yen per dollar, and sell them at a rate of 108 yen per dollar, you can obtain (108 - 100) × 1000 = 8000 yen.

Write a program which reads values of a currency $R_t$ at a certain time $t$ ($t=0,1,2,...n-1$), and reports the maximum value of $R_j-R_i$ where $j>i$ .

Input
The first line contains an integer $n$. In the following $n$ lines, $R_t$ ($t=0,1,2,...n-1$) are given in order.

Output
Print the maximum value in a line.

Constraints
$2\le n\le 200,000$
$1\le R_t\le 10^9$

Sample Input 1

6
5
3
1
3
4
3

Sample Output 1

3

Sample Input 2

3
4
3
2

Sample Output 2

-1

解法一 穷举
My code:

#include<iostream>
using namespace std;
long long int r[200005];

int main(){
	int i,j,n;
	long long int maxv=-10e9;
	cin>>n;
	for(int t=0;t<n;t++) cin>>r[t];
	for(j=1;j<n;j++)
		for(i=0;i<j;i++)
			maxv=max(maxv,r[j]-r[i]);
	cout<<maxv<<endl;
	return 0;
}

这种办法我一开始就否定了，他前面刚讲复杂度，哪里可能让你暴力解，这肯定超时了(*￣3￣)╭
此算法复杂度为O(n²)

解法二 记忆化搜索
My code:

#include<iostream>
using namespace std;

int main(){
	int n;
	long long int r,maxv=-10e9,minv;
	cin>>n>>r;
	minv=r;
	for(int i=1;i<n;i++) {
		cin>>r;
		maxv=max(maxv,r-minv);
		minv=min(minv,r);
	}
	cout<<maxv<<endl;
	return 0;
}

此算法复杂度为O(n)，同时优化了时间复杂度和空间复杂度
这个神奇的aizuoj判定超级严格，就输出一个数，少一个回车都不行＞︿＜
不过数学公式就是LaTeX，题面复制过来接能用这点很棒(￣▽￣)

排序

看前面内容太少，续上下一章
排序处理方便我们处理数据，一般会在有多个属性的表内排序，这一操作可以认为是一种属性Sort Key。同时，排序算法需要考虑的有：

• 复杂度和稳定性（稳定性指存在多个相同数据参与排序时保持原来顺序的能力）
• 是否需要额外内存
• 数据特征是否会影响复杂度

Insertion Sort????

Write a program of the Insertion Sort algorithm which sorts a sequence A in ascending order. The algorithm should be based on the following pseudocode:

for i = 1 to A.length-1
    key = A[i]
    /* insert A[i] into the sorted sequence A[0,...,j-1] */
    j = i - 1
    while j >= 0 and A[j] > key
        A[j+1] = A[j]
        j--
    A[j+1] = key

Note that, indices for array elements are based on 0-origin.

To illustrate the algorithms, your program should trace intermediate result for each step.

Input
The first line of the input includes an integer N, the number of elements in the sequence.

In the second line, N elements of the sequence are given separated by a single space.

Output
The output consists of N lines. Please output the intermediate sequence in a line for each step. Elements of the sequence should be separated by single space.

Constraints
1 ≤ N ≤ 100

Sample Input 1

6
5 2 4 6 1 3

Sample Output 1

5 2 4 6 1 3
2 5 4 6 1 3
2 4 5 6 1 3
2 4 5 6 1 3
1 2 4 5 6 3
1 2 3 4 5 6

Sample Input 2

3
1 2 3

Sample Output 2

1 2 3
1 2 3
1 2 3

My code:

#include<iostream>
using namespace std;

void prt(int a[],int n){
	for(int i=0;i<n;i++) cout<<a[i]<<' ';
	cout<<'b'<<endl;
}

void insertionsort(int A[],int n){
	int i,j,key;
	for( i = 1; i < n; i++){
		key = A[i];
    	j = i - 1;
    	while ( j >= 0 and A[j] > key){
       		A[j+1] = A[j];
        	j--;
        }
    	A[j+1] = key;
    	prt(A,n);
    }
}

int main(){
	int n,a[105];
	cin>>n;
	for (int i=0;i<n;i++) cin>>a[i];
	prt(a,n);
	insertionsort(a,n);
	return 0;
}

Bubble Sort????

Write a program of the Bubble Sort algorithm which sorts a sequence A in ascending order. The algorithm should be based on the following pseudocode:

BubbleSort(A)
	for i = 0 to A.length-1
 		for j = A.length-1 downto i+1
			if A[j] < A[j-1]
				swap A[j] and A[j-1]

Note that, indices for array elements are based on 0-origin.

Your program should also print the number of swap operations defined in line 4 of the pseudocode.

Input
The first line of the input includes an integer N, the number of elements in the sequence.

In the second line, N elements of the sequence are given separated by spaces characters.

Output
The output consists of 2 lines.

In the first line, please print the sorted sequence. Two contiguous elements of the sequence should be separated by a space character.

In the second line, please print the number of swap operations.

Constraints
1 ≤ N ≤ 100

Sample Input 1

5
5 3 2 4 1

Sample Output 1

1 2 3 4 5
8

Sample Input 2

6
5 2 4 6 1 3

Sample Output 2

1 2 3 4 5 6
9

My code:

#include<iostream>
using namespace std;

void prt(int a[],int n){
	for(int i=0;i<n;i++) cout<<a[i]<<' ';
	cout<<'b'<<endl;
}

void BubbleSort(int A[],int n){
	int i,j,k=0;
	for (i = 0 ;i < n; i++)
 		for (j = n-1; j > i;j--)
			if (A[j] < A[j-1]){
				swap(A[j],A[j-1]);
				k++;
			}
	prt(A,n);
	cout<<k<<endl;
}

int main(){
	int a[105],n;
	cin>>n;
	for(int i=0;i<n;i++)cin>>a[i];
	BubbleSort(a,n);
	return 0;
}

这个代码我本地测试良好，就是不知道它哪里有问题，过不了oj /_

Selection Sort????

Write a program of the Selection Sort algorithm which sorts a sequence A in ascending order. The algorithm should be based on the following pseudocode:

SelectionSort(A)
	for i = 0 to A.length-1
	    mini = i
	    for j = i to A.length-1
	        if A[j] < A[mini]
	            mini = j
	    swap A[i] and A[mini]

Note that, indices for array elements are based on 0-origin.

Your program should also print the number of swap operations defined in line 6 of the pseudocode in the case where i ≠ mini.

Input
The first line of the input includes an integer N, the number of elements in the sequence.

In the second line, N elements of the sequence are given separated by space characters.

Output
The output consists of 2 lines.

In the first line, please print the sorted sequence. Two contiguous elements of the sequence should be separated by a space character.

In the second line, please print the number of swap operations.

Constraints
1 ≤ N ≤ 100

Sample Input 1

6
5 6 4 2 1 3

Sample Output 1

1 2 3 4 5 6
4

Sample Input 2

6
5 2 4 6 1 3

Sample Output 2

1 2 3 4 5 6
3

My code:

#include<iostream>
using namespace std;

void prt(int a[],int n){
	for(int i=0;i<n;i++) cout<<a[i]<<' ';
	cout<<'b'<<endl;
}

void SelectionSort(int A[],int n){
	int i,j,k=0,minj;
	for (i = 0 ;i < n; i++){
 		mini = i;
 		for (j = i ;j < n; j++)
	        if (A[j] < A[mini])
	            minj = j;
		swap(A[i] , A[minj]);
		if(i!=minj)k++;
	}
	prt(A,n);
	cout<<k<<endl;
}

int main(){
	int a[105],n;
	cin>>n;
	for(int i=0;i<n;i++)cin>>a[i];
	SelectionSort(a,n);
	return 0;
}

Stable Sort????

Let’s arrange a deck of cards. There are totally 36 cards of 4 suits(S, H, C, D) and 9 values (1, 2, … 9). For example, ‘eight of heart’ is represented by H8 and ‘one of diamonds’ is represented by D1.

Your task is to write a program which sorts a given set of cards in ascending order by their values using the Bubble Sort algorithms and the Selection Sort algorithm respectively. These algorithms should be based on the following pseudocode:

BubbleSort(C)
	for i = 0 to C.length-1
	    for j = C.length-1 downto i+1
	        if C[j].value < C[j-1].value
	            swap C[j] and C[j-1]
SelectionSort(C)
	for i = 0 to C.length-1
	    mini = i
	    for j = i to C.length-1
	        if C[j].value < C[mini].value
	            mini = j
	    swap C[i] and C[mini]

Note that, indices for array elements are based on 0-origin.

For each algorithm, report the stability of the output for the given input (instance). Here, ‘stability of the output’ means that: cards with the same value appear in the output in the same order as they do in the input (instance).

Input
The first line contains an integer N, the number of cards.

N cards are given in the following line. Each card is represented by two characters. Two consecutive cards are separated by a space character.

Output
In the first line, print the arranged cards provided by the Bubble Sort algorithm. Two consecutive cards should be separated by a space character.

In the second line, print the stability (“Stable” or “Not stable”) of this output.

In the third line, print the arranged cards provided by the Selection Sort algorithm. Two consecutive cards should be separated by a space character.

In the fourth line, print the stability (“Stable” or “Not stable”) of this output.

Constraints
1 ≤ N ≤ 36

Sample Input 1

5
H4 C9 S4 D2 C3

Sample Output 1

D2 C3 H4 S4 C9
Stable
D2 C3 S4 H4 C9
Not stable

Sample Input 2

2
S1 H1

Sample Output 2

S1 H1
Stable
S1 H1
Stable

预备小知识：冒泡排序是稳定排序（前提是不在比较符上加等于）

My code:

#include<iostream>
using namespace std;
struct card {char suit;int value;};

void bub(struct card A[],int n){
	int i,j;
	for (i=0;i<n;i++)
 		for (j=n-1;j>i;j--)
			if (A[j].value<A[j-1].value){			//就是这里不要有等于，那相同数据顺序不会变
				card t=A[j];A[j]=A[j-1];A[j-1]=t;
			}
}

void slc(struct card A[],int n){
	int i,j,minj;
	for (i = 0 ;i < n; i++){
 		minj=i;
 		for (j = i ;j < n; j++)
	        if (A[j].value< A[minj].value)
	            minj=j;
	    card t=A[j];A[j]=A[minj];A[minj]=t;
	}
}

void prt(struct card a[],int n){
	for(int i=0;i<n;i++){
		if(i) cout<<' ';
		cout<<a[i].suit<<a[i].value;
	}
	cout<<endl;
}

bool cmp(struct card a1[],struct card a2[],int n){
	for(int i=0;i<n;i++)
		if(a1[i].suit==a2[i].suit) return true;
	return false;
}

int main(){
	card a1[105],a2[105];
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a1[i].suit>>a1[i].value;
		a2[i]=a1[i];
	}
	bub(a1,n);slc(a2,n);
	prt(a1,n);
	cout<<"Stable"<<endl;
	prt(a2,n);
	if(cmp(a1,a2,n)) cout<<"Stable"<<endl;
	else cout<<"Not stable"<<endl;
	return 0;
}

看起来老长一串，其实没有难度，把前面的模板套进来用即可

Shell Sort????

言外之意：今天太晚了，明天再想嘛(っ °Д °)っ
好吧 啊哈哈哈哈哈哈哈嗝

最后

以上就是土豪小甜瓜为你收集整理的2021.1.6寒假打卡Day3寒假打卡Day3的全部内容，希望文章能够帮你解决2021.1.6寒假打卡Day3寒假打卡Day3所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。