每日刷题（四十五）
蓝桥杯第九届C语言B组总决赛习题
习题A：换零钞
文章图片
C暴力枚举
这个题算简单，直接暴力枚举法
#includeint main()
{
int i, j;
for(i = 1;
i <= 200;
i++)
for(j = 1;
j < 40;
j++)
if(i + 10 * 2 * i + 5 * j == 200)
printf("5元：%d, 2元：%d, 1元：%d, total tickets: %d\n", j, 10 * i, i, i + 10 * i + j);
return 0;
}
运行结果如下：
文章图片
故填74
C++暴力枚举代码
#include
using namespace std;
int main()
{
int ans = 0;
//1元的纸钞数
for(int i = 1;
i <= 10;
i++)
{
for(int j = 1;
j < 40;
j++)
{
if(21 * i + j * 5 == 200)
{
ans = j + 11 * i;
break;
}
if(21 * i + j * 5 > 200)
{
break;
}
}
}
cout << ans << endl;
return 0;
}
文章图片
郑未题解
【每日刷题———蓝桥杯真题|蓝桥杯2018第九届C语言B组省赛总决赛习题题解——习题A.换零钞（暴力枚举法）】妈耶，太复杂了，感兴趣的同学继续看吧
#include
#include
using namespace std;
class ExtGcd {
public :
long x;
long y;
long gcd(long m, long n) {
return n == 0 ? m : gcd(n, m % n);
}/**
* 最小公倍数lowest common multiple (LCM)
* @param a
* @param b
* @return
*/
long lcm(long a, long b) {
return a * b / gcd(a, b);
}/**
* 扩展欧几里得
* 调用完成后xy是ax+by=gcd(a,b)的解*/
long ext_gcd(long a, long b) {if (b == 0) {
x = 1;
y = 0;
return a;
}
long res = ext_gcd(b, a % b);
//x,y已经被下一层递归更新了
long tmp = x;
//备份x
x = y;
//当前层的x
y = tmp - a / b * y;
//当前层的y
return res;
}/**
* 线性方程
* ax+by=m 当m时gcd(a,b)倍数时有解
* 等价于ax = m mod b*/
long linearEquation(long a, long b, long m) {
long d = ext_gcd(a, b);
//m不是gcd(vis,b)的倍数,这个方程无解
if (m % d != 0) {
throw exception();
}
long n = m / d;
//约一下,考虑m是d的倍数
x *= n;
y *= n;
return d;
}/**
* x = m1(%b1)
*= m2(%b2)
*= m3(%b3)
*x+b1y1=m1 (1)
*x+b2y2=m2 (2)
*两式相减==> b1y1 - b2y2 = m1 - m2这是一个线性方程,可解出y1 <--- linearEquation(b1,-b2,m1-m2)
*带回(1),得特解x0 = m1-b1*y1 --> 解系 x = x0 + k*lcm(b1,b2)，为什么呢？特解增加b1的k倍满足(1)增加b2的k倍满足(2)，那就干脆增加lcm(b1,b2)的k倍
*于是得一个新方程 ：x = x0 (mod lcm(b1,b2)) …… 继续
**/
long linearEquationGroup(long *m, long *b) {
int len = sizeof(m) / sizeof(long);
if (len == 0 && m[0] == 0) return b[0];
long m1 = m[0];
long b1 = b[0];
for (int i = 1;
i < len;
i++) {
long m2 = m[i];
long b2 = b[i];
long d = linearEquation(b1, -b2, m1 - m2);
//现在的static x是y1,用y1求得一个特解
long y1 = x;
long x0 = m1 - b1 * y1;
long lcm = b1 * b2 / d;
//这是新的b
m1 = (x0 % lcm + lcm) % lcm;
//x0变成正数
b1 = lcm;
}
//合并完之后,只有一个方程 : X mod b1 = m1
while (m1 < 0)
m1 += b1;
return m1;
}/**
* 求逆元
* ax = 1 (% mo),gcd(a,mo)=1
* ax+mo*y=1
* */
long inverseElement(long a, long mo) {long d = linearEquation(a, mo, 1);
//ax+mo*y=1
x = (x % mo + mo) % mo;
//保证x>0
return d;
}
};
int main(int argc, const char * argv[]) {
ExtGcd util;
util.linearEquation(21,5,200);
cout<< util.x<<""< 如果喜欢我的文章，请记得一键三连哦，点赞关注收藏，你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 ！！！↖(▔▽▔)↗感谢支持，下期更精彩！！！
推荐阅读
- 蓝桥杯算法训练|蓝桥杯算法训练 数字游戏 C语言实现
- 蓝桥杯|蓝桥杯——算法训练——进击的青蛙
- 笔记|第十二届蓝桥杯——Java软件开发（省赛）（括号序列（笔记15））
- CS241可视化分析
- LeetCode编程题解法汇总|力扣解法汇总258-各位相加
- YY|【C语言】三子棋游戏与多子棋 (保姆级的实现过程)
- 《网络安全快速入门》|别让数据库的报错信息，暴露了网站的用户数据。
- 拓端tecdat|【视频】线性混合效应模型(LMM,Linear Mixed Models)和R语言实现案例
- PTA|【PTA乙级】【1096 大美数 (15 分)】