Aczy156

Algorithm11.0 数据结构 线性表

[TOC]

数据结构 线性表

约瑟夫问题

https://www.luogu.com.cn/problem/P1996

题目大意：有规则抽取特定位置索引

1、删除、首尾添加、排序等等 => vector

#include <iostream>
using namespace std;
int n, m, idx=0;
#include <vector>
vector<int> b;

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) b.push_back(i);
    while (b.size() > 1) {
        idx = (idx+m-1)%b.size();
        printf("%d ", b[idx]);
        b.erase(b.begin()+idx);
    }
    printf("%d\n", b[0]);
    return 0;
}

前&中&后缀

https://www.luogu.com.cn/problem/P1449

题目大意：解析前、中、后缀表达式，然后得到表达式的值的意思

1、前缀中缀后缀，表达式 => 栈

#include <iostream>
using namespace std;
#include <stack>
char ch;
int a, b, store;
stack<int> s;

int main() {
    while (ch != '@') {
        ch = getchar();
        switch (ch) {
            case '+':b=s.top();s.pop();a=s.top();s.pop();s.push(a+b);break;
            case '-':b=s.top();s.pop();a=s.top();s.pop();s.push(a-b);break;
            case '*':b=s.top();s.pop();a=s.top();s.pop();s.push(a*b);break;
            case '/':b=s.top();s.pop();a=s.top();s.pop();s.push(a/b);break;
            case '.':s.push(store);store=0;break;
            default:store=store*10+(ch-'0');break;
        }
    }
    printf("%d\n", s.top());
    return 0;
}
Posted on Feb 1, 2021