机试练习Day6-有深度的题目--真题

news/2024/11/20 17:31:29/

目录

    • 矩阵快速幂
      • 快速幂算法
      • 代码部分
    • 复数的集合
      • 优先队列
      • 运算符重载
      • 结构体构造函数
      • 代码部分

矩阵快速幂

在这里插入图片描述

快速幂算法

这个道理和转二进制很像：

例如：现在要求3的9次方，最关键的是如何表示9，我们可以选择让3乘9次，也就是3 * 3 * 3 * 3 * 3 * 3 * 3 * 3* 3；
但是如果是10000000000次方就会让效率很低，现在可以考虑用二进制表示9，也就是1001，刚开始K=9是奇数，那么转成二进制后，最后一位一定是1，只要在大于0的范围内出现1，就有意义。

KBA
913
933 * 3
4不变：3（3 * 3） *（ 3 * 3）
2不变：3（3 * 3 * 3 * 3 ）*（ 3 * 3 * 3 * 3）
13 * （3 * 3 * 3 * 3 * 3 * 3 * 3 * 3）（3 * 3 * 3 * 3 * 3 * 3 * 3 * 3）*（3 * 3 * 3 * 3 * 3 * 3 * 3 * 3）
0ENDEND

在这里插入图片描述

代码部分

#include <stdio.h>
void Calculation(int a[10][10], int b[10][10], int n)
{int c[10][10] = {0};//矩阵乘法for (int i = 0; i < n; i ++) {for (int j = 0; j < n; j ++) {for (int k = 0; k < n; k ++) {c[i][j] += a[i][k] * b[k][j];}}}for (int i = 0; i < n; i ++) {for (int j = 0; j < n; j ++) {a[i][j] = c[i][j];}}
}int main() {int n, k;int a[10][10];int b[10][10];while (scanf("%d %d", &n, &k) != EOF) {//读入矩阵到afor (int i = 0; i < n; i ++) for (int j = 0; j < n; j ++) scanf("%d", &a[i][j]);//构造单位矩阵for (int i = 0; i < n; i ++) {for (int j = 0; j < n; j ++) {if(i == j) b[i][j] = 1;else b[i][j] = 0;}}//核心while (k > 0){if (k % 2 == 1) Calculation(b, a, n);Calculation(a, a, n);k /= 2;}//输出计算结果for (int i = 0; i < n; i ++) {for (int j = 0; j < n; j ++) printf("%d ", b[i][j]);         printf("\n");}}
}

复数的集合

优先队列

  • priority_queue<Type, Container, Functional>
  • 一个带优先级的队列【队头的优先级最高】
  • empty 队列是否为空
  • push 插入元素到队尾
  • top 访问队头元素
  • pop 弹出队头元素
  • size 返回队列内元素个数

运算符重载

  • 运算符重载实质上是函数的重载。
  • 一般格式：函数类型 operator 运算符名称（形参表）{对运算符的重载处理}
  • 当运算符重载为类的成员函数时，函数的参数个数比原来的操作数个数要少一个（后置“++”，“–”除外），原因：类的this指针所指的对象默认穿进去。
  • 用const对成员函数进行声明，表示这个函数不会修改类中的任何数据成员。下面这个函数承载如果去掉const会报错：“this”参数的类型为“const comp”，但方法未标记为const。

报错信息如下：

编译错误
您提交的代码无法完成编译
a.cpp:43:32: warning: format specifies type 'int' but the argument has type 'std::priority_queue>, std::less>::size_type' (aka 'unsigned long') [-Wformat]
printf("SIZE = %d\n",myqueue.size());
~~ ^~~~~~~~~~~~~~
%lu
a.cpp:51:30: warning: format specifies type 'int' but the argument has type 'std::priority_queue>, std::less>::size_type' (aka 'unsigned long') [-Wformat]
printf("SIZE = %d\n",myqueue.size());
~~ ^~~~~~~~~~~~~~
%lu
In file included from a.cpp:1:
In file included from /usr/bin/../lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/c++/7.5.0/iostream:39:
In file included from /usr/bin/../lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/c++/7.5.0/ostream:38:
In file included from /usr/bin/../lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/c++/7.5.0/ios:42:
In file included from /usr/bin/../lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/c++/7.5.0/bits/ios_base.h:41:
In file included from /usr/bin/../lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/c++/7.5.0/bits/locale_classes.h:40:
In file included from /usr/bin/../lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/c++/7.5.0/string:48:
/usr/bin/../lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/c++/7.5.0/bits/stl_function.h:386:20: error: invalid operands to binary expression ('const comp' and 'const comp')
{ return __x < __y; }
~~~ ^ ~~~
/usr/bin/../lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/c++/7.5.0/bits/predefined_ops.h:143:23: note: in instantiation of member function 'std::less::operator()' requested here
{ return bool(_M_comp(*__it1, *__it2)); }
^
/usr/bin/../lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/c++/7.5.0/bits/stl_heap.h:222:8: note: in instantiation of function template specialization '__gnu_cxx::__ops::_Iter_comp_iter>::operator()<__gnu_cxx::__normal_iterator>>, __gnu_cxx::__normal_iterator>>>' requested here
if (__comp(__first + __secondChild,
^
/usr/bin/../lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/c++/7.5.0/bits/stl_heap.h:253:12: note: in instantiation of function template specialization 'std::__adjust_heap<__gnu_cxx::__normal_iterator>>, long, comp, __gnu_cxx::__ops::_Iter_comp_iter>>' requested here
std::__adjust_heap(__first, _DistanceType(0),
^
/usr/bin/../lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/c++/7.5.0/bits/stl_heap.h:320:9: note: in instantiation of function template specialization 'std::__pop_heap<__gnu_cxx::__normal_iterator>>, __gnu_cxx::__ops::_Iter_comp_iter>>' requested here
std::__pop_heap(__first, __last, __last, __cmp);
^
/usr/bin/../lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/c++/7.5.0/bits/stl_queue.h:633:7: note: in instantiation of function template specialization 'std::pop_heap<__gnu_cxx::__normal_iterator>>, std::less>' requested here
std::pop_heap(c.begin(), c.end(), comp);
^
a.cpp:42:19: note: in instantiation of member function 'std::priority_queue>, std::less>::pop' requested here
myqueue.pop();
^
/usr/bin/../lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/c++/7.5.0/bits/stl_pair.h:454:5: note: candidate template ignored: could not match 'pair' against 'const comp'
operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
^
/usr/bin/../lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/c++/7.5.0/bits/stl_iterator.h:308:5: note: candidate template ignored: could not match 'reverse_iterator' against 'const comp'
operator<(const reverse_iterator<_Iterator>& __x,
^
/usr/bin/../lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/c++/7.5.0/bits/stl_iterator.h:346:5: note: candidate template ignored: could not match 'reverse_iterator' against 'const comp'
operator<(const reverse_iterator<_IteratorL>& __x,
^
/usr/bin/../lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/c++/7.5.0/bits/stl_iterator.h:1145:5: note: candidate template ignored: could not match 'move_iterator' against 'const comp'
operator<(const move_iterator<_IteratorL>& __x,
^
/usr/bin/../lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/c++/7.5.0/bits/stl_iterator.h:1151:5: note: candidate template ignored: could not match 'move_iterator' against 'const comp'
operator<(const move_iterator<_Iterator>& __x,
^
a.cpp:15:8: note: candidate function not viable: 'this' argument has type 'const comp', but method is not marked const
bool operator < (comp c) //运算符重载
^
2 warnings and 1 error generated.

结构体构造函数

【此处使用的是有参数版本】

  • 首先注意结尾处没有分号
  • 是初始化函数的简版：为了验证这个说法正确，我在源代码的基础上做了修改，如下所示：
struct comp{int real;int imag;//comp(int a,int b):real(a),imag(b){}comp(int a,int b){this->real=a;this->imag=b;}bool operator < (comp c) const //运算符重载{if(real*real+imag*imag==c.real*c.real+c.imag*c.imag)return imag > c.imag;//题目中并没有指出两个复数模一样大该如何计算，所以改为小于号也通过了else return real*real+imag*imag < c.real*c.real+c.imag*c.imag;//模小才为小}
};

在这里插入图片描述

代码部分

#include<iostream>
#include<queue>
#include<string>
using namespace std;struct comp{int real;int imag;comp(int a,int b):real(a),imag(b){} //有参数结构体构造函数bool operator < (comp c) const //运算符重载{if(real*real+imag*imag == c.real*c.real+c.imag*c.imag)return imag > c.imag;//题目中并没有指出两个复数模一样大该如何计算，所以改为小于号也通过了else return real*real+imag*imag < c.real*c.real+c.imag*c.imag;//模小才为小}
};int main()
{int n;while(scanf("%d",&n)!=EOF){priority_queue<comp> myqueue;while(n--){string str;cin>>str;if(str=="Pop"){if(myqueue.empty())printf("empty\n");else{printf("%d+i%d\n",myqueue.top().real,myqueue.top().imag);myqueue.pop();printf("SIZE = %d\n",myqueue.size());}}else{int a,b;scanf("%d+i%d",&a,&b);myqueue.push(comp(a,b));printf("SIZE = %d\n",myqueue.size());}}}
}

http://www.ppmy.cn/news/34785.html

相关文章

第十四届蓝桥杯三月真题刷题训练——第 20 天

第十四届蓝桥杯三月真题刷题训练——第 20 天

目录 第 1 题&#xff1a;纸张尺寸 问题描述 输入格式 输出格式 样例输入1 样例输出1 样例输入 2 样例输出 2 运行限制 代码&#xff1a; 解析&#xff1a; 第 2 题&#xff1a;最大数字 第 3 题&#xff1a;全排列的价值_递推公式 问题描述 输入格式 输出格式…
阅读更多...
MD5加密竟然不安全，应届生表示无法理解？

MD5加密竟然不安全，应届生表示无法理解？

前言 近日公司的一个应届生问我&#xff0c;他做的一个毕业设计密码是MD5加密存储的&#xff0c;为什么密码我帮他调试的时候&#xff0c;我能猜出来明文是什么&#xff1f; 第六感&#xff0c;是后端研发的第六感&#xff01; 正文 示例&#xff0c;有个系统&#xff0c;前…
阅读更多...
电路设计的一些概念

电路设计的一些概念

锁存器的产生 论述1 (转)时序电路&#xff0c;生成触发器&#xff0c;触发器是有使能端的&#xff0c;使能端无效时数据不变&#xff0c;这是触发器的特性。 组合逻辑&#xff0c;由于数据要保持不变&#xff0c;只能通过锁存器来保存。 第一个代码&#xff0c;由于是时序逻…
阅读更多...
第二十一天 数据库开发-MySQL

第二十一天 数据库开发-MySQL

目录 数据库开发-MySQL 前言 1. MySQL概述 1.1 安装 1.2 数据模型 1.3 SQL介绍 1.4 项目开发流程 2. 数据库设计-DDL 2.1 数据库操作 2.2 图形化工具 2.3 表操作 3. 数据库操作-DML 3.1 增加(insert) 3.2 修改(update) 3.3 删除(delete) 数据库开发-MySQL 前言 …
阅读更多...
C语言之按位取反~(七十一)

C语言之按位取反~(七十一)

计算机存储数据基本知识计算机中二进制数包括&#xff08;正数和负数&#xff09;是以补码形式存储。符号位&#xff1a;补码的最左侧首位是符号位&#xff0c;0表示正数&#xff0c;1表示负数。二进制有三种形式&#xff1a;原码、反码、补码。正数的补码和反码&#xff1a;是…
阅读更多...
四级数据库工程师 刷真题错题整理（三）数据库原理

四级数据库工程师 刷真题错题整理（三）数据库原理

1.数据模型是对现实世界进行抽象的工具&#xff0c;它按算机系统的观点模于提数据库系统中信息表示和操作手段的形式框架&#xff0c;主要用于 DBMS 的实现&#xff0c;是数据库系统的核心和基础。其中&#xff0c;数据操作是对数据间的动态行为。 2.数据库的型是稳定的&#…
阅读更多...
并查集、并查集+离线、并查集+倒叙回答

并查集、并查集+离线、并查集+倒叙回答

文章目录并查集[200. 岛屿数量](https://leetcode.cn/problems/number-of-islands/)[721. 账户合并](https://leetcode.cn/problems/accounts-merge/)并查集 离线计算[1697. 检查边长度限制的路径是否存在](https://leetcode.cn/problems/checking-existence-of-edge-length-l…
阅读更多...
SpringCloud学习笔记（一）认识微服务

SpringCloud学习笔记（一）认识微服务

一、微服务技术栈 二、单体架构和分布式架构的区别 1、单体架构&#xff1a; 将业务的所有功能集中在一个项目中开发&#xff0c;打成一个包进行部署 优点&#xff1a;架构简单&#xff0c;部署成本低缺点&#xff1a;耦合度高 2、分布式架构&#xff1a; 根据业务功能对系统…
阅读更多...
最新文章

Copyright @ 2022~2023