寒假程序设计与算法训练3——枚举、模拟、贪心专项训练（2020-01-03）

本文主要是介绍寒假程序设计与算法训练3——枚举、模拟、贪心专项训练（2020-01-03），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

T1：回文数

T1：我的参考程序

#include <iostream>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 1e4 + 5;
typedef long long ll;
int n, cnt, step, num[maxn];
char a[maxn], cp[maxn];

bool isOK()
{
	for(int i = 0, j = cnt - 1; i < cnt && j >= 0; ++i, --j)
	{
		if(a[i] != a[j])
			return false;
	}
	return true;
}

void process()
{
	for(int i = 0; i < cnt; ++i)
		cp[i] = a[i];
	reverse(cp, cp + cnt);
	for(int i = 0; i < cnt; ++i)
	{
		int add1 = isdigit(cp[i]) ? cp[i] - '0' : cp[i] - 'A' + 10;
		int add2 = isdigit(a[i]) ? a[i] - '0' : a[i] - 'A' + 10;
		int addv = add1 + add2;
		num[i] = addv;
	}
	for(int i = 0; i < cnt; ++i)
	{
		if(num[i] >= n)
		{
			num[i + 1] += num[i] / n;
			num[i] %= n;
		}
	}
	while(!num[cnt] && cnt > 0)
		cnt--;
	for(int i = cnt; i >= 0; --i)
	{
		a[cnt - i] = num[i] < 10 ? num[i] + '0' : num[i] - 10 + 'A';
		cp[i] = '\0';
		num[i] = 0;
	}
	cnt++;
}

int main()
{
	bool flag = false;
	cin >> n >> a;
	cnt = strlen(a);
	while(cnt < maxn)
	{
		if(isOK())
		{
			flag = true;
			break;
		}
		process();
		step++;
	}
	if(flag)
		cout << "STEP=" << step << endl;
	else
		cout << "Impossible!" << endl;
	return 0;
}

T1：算法分析与设计

这题还是很简单的，但是也是很有必要练习的，进制转换、数组模拟数的运算过程，一直以来是程序设计与算法竞赛常考的问题。这题的关键是搞清楚10以内的进制和10以上的进制在加合的时候，如何应对。我的应对方法不算好，开了三个数组，其实cp数组完全是没必要的，一个字符数组、一个模拟运算的整型数组即可。

T2：数与连分数

T2：预备知识——连分数

以上内容来自维基百科，我认为的连分数解题的关键，如果想知道更多，请点我~

T2：我的参考程序

#include <iostream>
#include <string>
#include <queue>
#include <sstream>
#include <cstdio>
#include <stack>
using namespace std;

int gcd(const int& x, const int& y)
{
    return 0 == y ? x : gcd(y, x % y);
}

inline void Swap(int& x, int& y)
{
    int t = x;
    x = y;
    y = t;
}

int main()
{
    string str;
    while(getline(cin, str))
    {
        if(str.length() <= 0)
            continue;
        if('[' == str[0])
        {
            stringstream ss(str);
            int val;
            char ch;
            stack<int> s;
            ss >> ch;
            while(ss >> val >> ch)
                s.push(val);
            int f_dw = 0, f_up = 1;
            while(!s.empty())
            {
                int inp = s.top();
                s.pop();
                f_dw += f_up * inp;
                Swap(f_up, f_dw);
            }
            int _gcd = gcd(f_up, f_dw);
            f_up /= _gcd;
            f_dw /= _gcd;
            if(1 != f_dw)
                printf("%d/%d\n", f_up, f_dw);
            else
                printf("%d\n", f_up);
        }
        else
        {
            int f_up, f_dw;
            char ch;
            stringstream ss(str);
            ss >> f_up >> ch >> f_dw;
            int _gcd = gcd(f_up, f_dw);
            f_up /= _gcd;
            f_dw /= _gcd;
            queue<int> res;
            while(1)
            {
                int Int = f_up / f_dw;
                res.push(Int);
                f_up -= Int * f_dw;
                if(0 == f_up)
                    break;
                Swap(f_up, f_dw);
            }
            if(1 == (int)res.size())
                printf("[%d]\n", res.front());
            else
            {
                printf("[%d;", res.front());
                res.pop();
                while((int)res.size() > 1)
                {
                    printf("%d,", res.front());
                    res.pop();
                }
                printf("%d]\n", res.front());
                res.pop();
            }
        }
    }
    return 0;
}

T2：算法分析与设计

这题我感觉难度还是不错的，算比较有难度了（我太菜……）。需要一定的耐心和细心！

1、分数转成连分数的方法：

首先向下取整，得到整数部分，然后分数减去整数部分，得到真分数。如此往复，直到分数减去整数部分后为0，可以证明，有理数一定是存在有限次数达到分数为0（其实也就是分子为0）的情况的。证明方法就是辗转相除法，和欧几里得定理无差。

2、连分数转成分数的方法：

最后进入的整数是最底下也是最先开始计算的分数分母，而所有的分子都是1。这种后入先出的结构我们使用栈去处理，然后最难的就是如何设计递归，让每层连分数都能够被正确处理？

一开始，我们让分子为1，这个是显然的，本来连分数的分子都是1，但是分母如何初始化？我们考虑到每次计算都会让分数倒过来，所以先让分母为0，然后计算当前这一步的分子，也就是 f_dw += Inp * f_up，此时此刻，分数就出来了，然后反复计算即可。

这篇关于寒假程序设计与算法训练3——枚举、模拟、贪心专项训练（2020-01-03）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！