Java教程

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

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

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)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!