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

朱雀 2024-03-26 21:26 14阅读 0赞

#### 目录 ####

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

### 矩阵快速幂 ###

![在这里插入图片描述][4281de43e08b40b0b336f8abcb542eba.png_pic_center]

#### 快速幂算法 ####

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

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

![在这里插入图片描述][e9cff8439fbd49418027c25827542cf4.png_pic_center]

#### 代码部分 ####

#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) 
    	{
        
    
            //读入矩阵到a
            for (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;//模小才为小
      }
    };

![在这里插入图片描述][483840416c934d80aad0567ea69c1b19.png_pic_center]

#### 代码部分 ####

#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());
          }
        }
      }
    }

[4281de43e08b40b0b336f8abcb542eba.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/398296e555d4411681c999909bf2ba97.png
[e9cff8439fbd49418027c25827542cf4.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/e812583479ee457f9049383cf0bbc029.png
[483840416c934d80aad0567ea69c1b19.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/90fff307b93f47f6ad9eb83a51f8289e.png