王道机试C++第 5 章 数据结构一：向量vector和蓝桥杯13年两个程序 Day31

（ 2 ） vector 的状态

        vector 中用做判断的状态通常有两个：一个是返回当前向量是否为空的 empty() ，另一个是返回当前向量元素个数的 size() 。

（ 3 ） vector 尾部元素的添加或删除

       定义一个向量后，如果要向其尾部添加新的元素，或删除尾部的元素，那么就要使用 push_back()和 pop_back() 。

（ 4 ） vector 元素的访问

① 可以像数组一般通过元素下标进行访问，下标从 0 到 size()-1 。

② 可以通过迭代器进行访问，迭代器类似于指针。

（ 5 ） vector 元素操作

vector 中的常用元素操作包括：在任意位置插入元素的 insert() ，在任意位置删除元素的erase()，将向量清空的 clear() 。

（ 6 ） vector 迭代器操作

vector 中常用的迭代器操作包括：返回向量中的首元素的迭代器 begin() ，返回向量中尾

元素后一个位置的迭代器 end() 。

一些基本的代码

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    vector<int> myVector;
    myVector.push_back(1);//给数组尾部扩容 
    
    // 向尾部逐一添加元素0到4 
    for (int i = 0; i < 5; ++i) {
        myVector.push_back(i);
    }
    
    vector<int>vec1{1,2,3} ;//创建一个动态数组开始就赋值 
    for(unsigned i=0;i<vec.size();++i){
    	printf("vec1[%d]=%d\n",i,vec1[i])
	}
    
    // 头部插入 3 个 15
    myVector.insert(myVector.begin(), 3, 15);
 
    // 移除尾部元素
    myVector.pop_back();
 
    // 打印向量元素
    for (int i = 0; i < myVector.size(); ++i) {
        printf("%d ", myVector[i]);
    }
    printf("\n");
 
    // 访问第 5 个元素
    printf("the 5th element of myVector: %d\n", myVector[4]);
 
    // 打印向量大小
    printf("the size of myVector: %d\n", myVector.size());
 
    // 删除第 5 后续的元素
    myVector.erase(myVector.begin() + 5, myVector.end());
 
    // 遍历向量并打印
    for (vector<int>::iterator it = myVector.begin(); it != myVector.end(); it++) {
        printf("%d ", *it);
    }
    printf("\n");
 
    // 清空向量
    myVector.clear();
 
    return 0;
}

2．向量的应用

例题 5.1 完数与盈数（清华复试上机题）

题目描述：

代码表示：

#include <bits/stdc++.h>
using namespace std;
 
int Sum(int i){//传入的是i 
    int sum=0;
    for(int j=1;j<i;++j){
    	if(i%j==0){
    		sum=sum+j;
		}
	}
	return sum;
}
 
int main() {
    vector<int>evec;//完数 
    vector<int>gvec;//盈数 
    for(int i=2;i<=60;++i){
    	if(i==Sum(i)){//数等于约数和 
    		evec.push_back(i);
		}
		else if(i<Sum(i)){
		    gvec.push_back(i);
		}
	}
	printf("E:");
	for(int i=0;i<evec.size();++i){
		printf(" %d",evec[i]);
	}
	printf("\n");
	printf("G:");
	for(int i=0;i<gvec.size();++i){
		printf(" %d",gvec[i]);
	}
	printf("\n");
    return 0;
}

---

[蓝桥杯 2013 省 B] 带分数

题目描述

100 可以表示为带分数的形式：100=3+69258 / 714  

还可以表示为：100=82+3546 / 197

注意特征：带分数中，数字 1 ~ 9 分别出现且只出现一次（不包含 0）。

类似这样的带分数，100 有 11 种表示法。

输入格式:从标准输入读入一个正整数 N(N<106)。

输出格式:程序输出数字 N用数码 1 ~ 9 不重复不遗漏地组成带分数表示的全部种数。

注意：不要求输出每个表示，只统计有多少表示法！

代码表示：

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    vector<int> vec;
    for (int i = 1; i <= 9; ++i) {
        vec.push_back(i);
    }
 
    int count = 0;
//使用do-while循环来进行全排列。在每次迭代中，使用两个嵌套的for循环来枚举数码的排列组合。
//变量i表示第一个数码的位置，变量j表示第二个数码的位置
    do {
        for (int i = 1; i <= 7; ++i) {
            for (int j = i + 1; j <= 8; ++j) {
//变量k来遍历数码的位置。通过不同的循环范围，将数码分别赋值给变量a、b和c。
//这样就得到了带分数的三个部分          	
                int a = 0, b = 0, c = 0;
                
                for (int k = 0; k < i; ++k) {
                    a = a * 10 + vec[k];
                }
                for (int k = i; k < j; ++k) {
                    b = b * 10 + vec[k];
                }
                for (int k = j; k < 9; ++k) {
                    c = c * 10 + vec[k];
                }
                
                if (a + b * 1.0 / c == n) {
                    count++;
                }
            }
        }
//next_permutation函数来获取向量vec的下一个排列
    } while (next_permutation(vec.begin(), vec.end()));
 
    cout << count << endl;
 
    return 0;
}

心的体会：

1、外层循环的变量i表示第一个数码的位置，范围是从1到7。内层循环的变量j表示第二个数码的位置，范围是从i+1到8。

通过这样的设置，确保了第二个数码的位置在第一个数码的位置之后，避免了重复计算相同的组合。这样，循环的组合可以覆盖所有可能的数码位置组合，例如，第一个数码在位置1，第二个数码在位置2、3、4、5、6、7、8；第一个数码在位置2，第二个数码在位置3、4、5、6、7、8；以此类推。在每个组合中，代码会根据数码的位置，将数码的值分别赋给变量a、b和c，然后进行特定的计算或操作。

2、next_permutation 是一个 C++ 标准库中的函数，用于在给定序列中生成下一个（字典序的）排列。它会修改输入序列，将其变为下一个排列，并返回 true；如果输入序列已经是最后一个排列，则将其变为第一个排列并返回 false。

这个函数一般用于排列组合等算法中，可以帮助我们遍历所有的排列方式。调用方法如下：

template <class BidirectionalIterator>

bool next_permutation (BidirectionalIterator first, BidirectionalIterator last);

其中 first 和 last 是表示范围的迭代器，函数会在 [first, last) 范围内生成下一个排列。

举个例子，如果我们有一个数组 {1, 2, 3}，初始时排列为 {1, 2, 3}，连续调用 next_permutation 函数将会得到以下排列：

1. {1, 3, 2}
2. {2, 1, 3}
3. {2, 3, 1}
4. {3, 1, 2}
5. {3, 2, 1}

当函数返回 false 时，表示已经遍历完所有排列，下一次调用时会重新开始。

3、do-while循环和while循环的主要区别在于条件的判断时机。do-while循环是先执行循环体中的代码，然后再判断条件是否满足，即至少执行一次循环体。而while循环是先判断条件是否满足，然后再执行循环体，可能一次都不执行。

如果在这段代码中，确保至少执行一次循环体是必要的，即希望在进入循环之前先执行一次计算或操作，那么使用do-while循环是合适的。

---

[蓝桥杯 2013 省 B] 翻硬币

题目背景:小明正在玩一个“翻硬币”的游戏。

题目描述:

桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零），比如可能情形是 **oo***oooo，如果同时翻转左边的两个硬币，则变为 oooo***oooo。现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币，那么对特定的局面，最少要翻动多少次呢？

输入格式:两行等长字符串，分别表示初始状态和要达到的目标状态，每行长度小于 1000。

数据保证一定存在至少一种方案可以从初始状态和要达到的目标状态。

输出格式:一个整数，表示最小操作步数。

代码表示：

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    string initial_state, target_state;//两个字符串变量 
    getline(cin, initial_state);
    getline(cin, target_state);
   
    int min_steps = 0;//最小操作步数 
    int size = initial_state.size();//初始状态字符串的长度 
//从第一个字符到倒数第二个字符（size - 1）  
    for (int i = 0; i < size - 1; i++) {
        if (initial_state[i] != target_state[i]) {
            initial_state[i] = (initial_state[i] == '*') ? 'o' : '*';
            initial_state[i + 1] = (initial_state[i + 1] == '*') ? 'o' : '*';
            min_steps++;
        }
    }
    
    cout << min_steps << endl;  
    return 0;
}

心得体会：