嵌入式Linux工程师笔试记录 -- 2020.8.5 (四)-阿南达文事网

嵌入式Linux工程师笔试记录 -- 2020.8.5 (四)

嵌入式Linux工程师笔试记录 – 2020.8.5 (四)
2017年广州代代星笔试题

嵌入式Linux工程师笔试记录 -- 四

1.递归方式计算4(1-1/3+1/5-1/7...)的近似值，直到括号最后一项绝对值小于10^-6为止。
2. 有N个人围成一圈，顺序排号。从第一个人开始报数(从1-3报数)，凡报到3的人退出圈子，问最后留下的人原来排在第几号。（要求用链表实现，代码中有一个实现链表的类，最好有异常处理，写c++代码）
- - 2020.8.23添加：v2.0版本
3.编写字符串类String的构造函数、析构函数和赋值函数。
- - 2020.8.23添加：v2.0版本
4.八皇后求解
- - 2020.8.23添加：v2.0版本

1.递归方式计算4(1-1/3+1/5-1/7…)的近似值，直到括号最后一项绝对值小于10^-6为止。

解析：此题关键在复杂度的考虑。

方法一（低精度情况下）：

/* 递归程序 */
#include <stdio.h>
/* 递归程序 */
double __process( int t ){if( t < 0 )return 0;int tmp = t/2;if( tmp%2 == 0 )// 1 5 9 ...return __process(t-2) + 1.0/t ;else // 3 7 11return __process(t-2) - 1.0/t ;
}
double process( long n ){if( n%2 == 0 ) // 如果是偶数n --;return 4*__process(n);
}
int main(){long n;printf("请输入精度(正整数)：");scanf("%ld" , &n);double t = process( n );printf("%.8lf\n",t);return 0;
}

结果：

此递归函数很难跑出来(顶多到10^-5)，递归层数太多，空间复杂度n，高精度下栈空间有点压力，操作系统也没法做多余的事情。使用二分法递归，空间复杂度降低为logn，可以达到的精度更高。

方法二(要求高精度情况下)：

#include <stdio.h>
/* 递归程序 */
/* 采用二分法 */
double __process( long l , long r ){if( l == r ) // 结束条件if( l/2%2 ) // 3 7 11 return -1.0 / l ;else // 1 5 9return 1.0 / l ;long mid = l + (r-l)/2 ; if( mid%2 == 0 )mid -- ;return __process( l , mid ) + __process( mid+2 , r ); 
}
double process( long n ){if( n%2 == 0 ) // 如果是偶数n --;return 4*__process( 1 , n );
}
int main(){long n;printf("请输入精度(正整数)：");scanf("%ld" , &n);double t = process( n );printf("%.8lf\n",t);return 0;
}

结果：

此程序精度达到了10^-8，到-9精度的时候死机了(时间复杂度裂开)。

2. 有N个人围成一圈，顺序排号。从第一个人开始报数(从1-3报数)，凡报到3的人退出圈子，问最后留下的人原来排在第几号。（要求用链表实现，代码中有一个实现链表的类，最好有异常处理，写c++代码）

解析：约瑟夫环问题，以及要求实现链表类
参考：
懒猫老师-C语言-链表作业2:约瑟夫环(三种方法)(猴子选大王)
约瑟夫环的三种解法（循环链表、数组、递归）
代码：

#include <iostream>
#include <stdlib.h>using namespace std;typedef struct Node{ // 节点int data;Node *next;
} Node;
class JosephCircle{
private:Node * head ; // 头结点Node * tail ; // 尾结点
public:JosephCircle():tail(NULL),head(NULL){}~JosephCircle(){// 释放堆空间 if(head == tail){delete head;}else{Node *p = head;head = head->next ;tail = head;delete p;}}void additem( int item ){// 添加一个结点  头插if(tail == NULL){ // 还未有结点tail = new Node;if(tail==NULL){cout << "new Node error" << endl; exit(-1); }tail->data = item;head = tail;tail->next = head;}else{ // tail != NULLNode * new_Node = new Node;if( new_Node ==NULL){cout << "new Node error" << endl; exit(-1); }new_Node->data = item;new_Node->next = head;head = new_Node;tail->next = head;}}int Eliminate( int step ){/* 报数到step的时候，移除，返回最后留下的人的排号 */Node *p = head;while(1){if( p->next == p ) // 剩下的最后一人break;for( int i = 1 ; i < step-1 ; i ++ ){  // 找到报数为step的人前一个人。p = p -> next;}/* 踢出 */Node *node = p->next;p->next = node->next;if( node == tail ) // 如果删了尾部结点tail = p;if( node == head ){ // 如果删除头结点head = p->next;tail->next = head;}delete node;p = p->next;	// 下一轮报数print();}return p->data;}void print(){Node *p = head ; while(p!=tail){cout << p->data << "->" ;p = p->next;}cout << p->data << endl;}
};int main(){int n ;cout << "请输入人数：" ;cin >> n ;JosephCircle list;for( int i = 0 ; i < n ; i ++ ){list.additem(n-i);}int result = list.Eliminate(3);cout << "结果为：" << result << endl;return 0;
}

结果：

2020.8.23添加：v2.0版本

类中主要包含插入和删除操作：

int JosephCircle( int n , int cnt ){Lst L;				// 初始化一个链表for( int i = n ; i > 0 ; i -- )L.push_front(i);		// 头插编号,最终为head->1->2->...->nNode* p = L.get_head();		// 获取head指针int i = 0;while( p->next != p ){p = p->next;if( ++i == cnt ){i = 0;p = L.erase( p );		// 删除一个编号，返回前一个指针}}int ret = p->value;return ret;
}

链表类建立：

#include <iostream>
#include <stdlib.h>
#include <string.h>
using namespace std;typedef struct Node{int value;Node *next;Node *pre;
} Node;class Lst{
public:Lst(){head = new Node;head->next = NULL;		// 指向第一个结点head->pre = NULL;		// 指向最后结点head->value = 0;}~Lst(){Node *p = head->next;while( p != NULL )p = erase(p);	// 删除返回前一个指针，删除完最后一个结点，返回NULLdelete head;head = NULL;}int push_front( int value ){Node *newNode = new Node;if( newNode == NULL )return -1;				// 插入错误newNode->value = value;if( head->next == NULL ){head->next = newNode;head->pre = newNode;newNode->next = newNode;newNode->pre = newNode;}else{ // head->next != NULLnewNode->next = head->next;head->next->pre = newNode;head->next = newNode;head->pre->next = newNode; // 第一个节点与最后一个结点循环newNode->pre = head->pre;}return  0;}Node * get_head(){return head;}Node * erase( Node * node ){if( node == NULL )return NULL;Node *p = node;p->pre->next = p->next;p->next->pre = p->pre;if( head->next == p ){// 第一个结点head->next = p->next;head->pre->next = p->next;}else if( head->pre == p ){// 最后一个结点head->pre = p->pre;head->next->pre = p->pre;}Node *ret = p->pre;if( ret == p )return NULL;	// 没有结点了delete p;p->next = NULL;p->pre = NULL;p = NULL;print();return ret;}void print(){Node *p = head->next;cout << "head" ;do{cout << "->";cout << p->value  ;	// 删除返回前一个指针，删除完最后一个结点，返回NULLp = p->next;}while(p != head->next);cout << endl;}private:Node * head;};int JosephCircle( int n , int cnt ){Lst L;				// 初始化一个链表for( int i = n ; i > 0 ; i -- )L.push_front(i);		// 头插编号,最终为head->1->2->...->nNode* p = L.get_head();		// 获取head指针int i = 0;while( p->next != p ){p = p->next;if( ++i == cnt ){i = 0;p = L.erase( p );		// 删除一个编号，返回前一个指针}}int ret = p->value;return ret;
}int main(){cout << "结果：" << JosephCircle( 10 , 3 ) << endl;return 0;
}

3.编写字符串类String的构造函数、析构函数和赋值函数。

已知 String类的原型如下：

class String {
public:String( const char * str = NULL );   	// 普通构造函数String( const String &other );   		// 拷贝构造函数~String(void);String & operate = (const String &other ); 	// 赋值函数
private:char * m_data;							// 保存的字符串
}

请编写上述四个函数：

#include <iostream>
#include <stdlib.h>
#include <string.h>
using namespace std;class String {
public:String( const char * str = NULL );   	// 普通构造函数String( const String &other );   		// 拷贝构造函数~String(void);String & operator = (const String &other ); 	// 赋值函数//测试用void print(){cout << m_data << endl;}
private:char * m_data;							// 保存的字符串
};// 普通构造函数
String::String( const char *str ){if( str == NULL ){m_data = new char[1] ;m_data[0] = '\0';}else{m_data = new char[strlen(str)+1];strcpy(m_data,str);}
}
String::String( const String &other ){m_data = new char(strlen(other.m_data)+1);strcpy(m_data,other.m_data);
}
String::~String(void){if(m_data!=NULL){delete [] m_data;m_data = NULL;}
}String & String::operator = (const String &other){if(this == &other){return *this;}delete[] m_data;m_data = new char[strlen(other.m_data)+1];strcpy(m_data,other.m_data);
}int main(){String a;a = "helloworld";a.print();String b(a);b.print();String c;c = a;c.print();return 0;
}

结果：

2020.8.23添加：v2.0版本

string的空间连续，并且每次修改长度，都预留传入值的长度的2倍，减少delete和new的操作次数

#include <iostream>
#include <stdlib.h>
#include <string.h>
using namespace std;class String {
public:String( const char * str = NULL );   	// 普通构造函数String( const String &other );   		// 拷贝构造函数~String(void);String & operator = (const String &other ); 	// 赋值函数//测试用void print(){cout << m_data << endl;}
private:char * m_data;							// 保存的字符串
};// 普通构造函数
String::String( const char *str ){if( str == NULL ){m_data = new char[1] ;m_data[0] = '\0';}else{m_data = new char[strlen(str)*2];strcpy(m_data,str);}
}
String::String( const String &other ){m_data = new char(strlen(other.m_data)*2);strcpy(m_data,other.m_data);
}
String::~String(void){if(m_data!=NULL){delete [] m_data;m_data = NULL;}
}String & String::operator = (const String &other){if(this == &other){return *this;}delete[] m_data;m_data = new char[strlen(other.m_data)*2];strcpy(m_data,other.m_data);
}int main(){String a;a = "helloworld";cout << a.c_str() << endl;String b(a);cout << b.c_str() << endl;String c;c = a;cout << c.c_str() << endl;return 0;
}

4.八皇后求解

每个皇后的同行、同列、同左斜、同右斜都不能有其他皇后。输出所有解。

解析：运用递归求解该题，按行放置皇后，无非就是两个情况， 1 要么检查发现该位置无冲突则放置皇后递归进入下一行放置；2 要么检查发现该位置有冲突/或者当前位置情况已经求解结束，递归进入下一列判断。

所以可以用两重递归解决该问题。

__递归程序( int **map , int cos , int row )
if  列大于棋盘列 达到递归结束条件 return 0
if  cos大于棋盘行达到递归结束条件，并获得一个解 printMap输出棋盘 ， return 0;
if  位置冲突判断 -- 位置合适放置皇后__递归程序( map , cos+1 , 0 ) ;  进入下一行判断恢复原状，从递归回来，说明当前位置的所有情况已经遍历完毕__递归程序(map , cos , row+1 ) ; 进入下一个位置判断

除此之外就只剩下两个简单的函数需要解决，如何判断该位置是否合适？如何输出棋盘？总的代码如下：

#include <stdio.h>// 棋盘大小
#define MAPLENGTH 8 void printMap( int * map );
int checkplace( int *map , int cos , int row );/* 递归函数 map为棋盘数组，cos和row为当前位置 */
void __process( int *map , int cos , int row ){if(row == MAPLENGTH)// 递归结束return  ;if(cos == MAPLENGTH){// 递归结束并获得一解printMap( map );return  ;}if( checkplace( map , cos , row ) ){// 如果位置合适map[cos*MAPLENGTH + row] = 1;	// 放置皇后__process( map , cos + 1 , 0 );	// 进入下一行判断map[cos*MAPLENGTH + row] = 0; 	// 恢复原状}__process( map , cos , row + 1 ) ; // 进入下一个位置判断}
/* 求解函数 n为棋盘大小 */
void process(){int map[MAPLENGTH*MAPLENGTH] = {0} ;__process( map , 0 , 0 );	//进入递归求解
}int checkplace( int *map , int cos , int row ){int i , j ;//判断同列是否有皇后for( i = 0 ; i < MAPLENGTH ; i ++ ){if( i == cos )continue;if( map[i*MAPLENGTH+row] )return 0;	// 冲突}//判断同列是否有皇后for( j = 0 ; j < MAPLENGTH ; j ++ ){if( j == row )continue;if( map[cos*MAPLENGTH+j] )return 0;	// 冲突}//判断同'\'是否有皇后i = cos ;j = row ;while(i&&j){i-- ; j--;	//同'\'左上角第一个位置}for(; i < MAPLENGTH && j < MAPLENGTH ; i ++ , j ++ ){if( i == cos )continue;if( map[i*MAPLENGTH+j] )return 0;	// 冲突}//判断同'/'是否有皇后i = cos ;j = row ;while(i<7&&j){i++ ; j--;	//同'/'左下角第一个位置}for(; i >= 0 && j < MAPLENGTH ; i -- , j ++ ){if( i == cos )continue;if( map[i*MAPLENGTH+j] )return 0;	// 冲突}return 1;	// 无冲突，位置合适
}void printMap( int * map ){static int cnt = 0 ; //计数解个数int i , j ;printf("第%d个解如下：\n" , ++cnt );for( i = 0 ; i < MAPLENGTH ; i ++ ){for( j = 0 ; j < MAPLENGTH ; j ++ ){if(map[i*MAPLENGTH+j]){printf("K");}else{printf("_");}}printf("\n");}
}int main(){process();return 0;
}

结果：

2020.8.23添加：v2.0版本

直接用一个8*8的数组表示浪费时间，并且每次checkplace都会遍历每个可能(O(n))。
根据懒猫老师的课程，起始可以用一个长度为8的数组表示每个皇后所在列，并且可以用三个数组表示行和斜线上存在皇后与否，使得checkplace判断只需三次(O©)

bool KingCol[8] ; 	// 	row,col处放了皇后 == KingCol[col] = true 
bool KingL[8*2];		//  == KingL[col+row] = true;
bool KingR[8*2];		//  == KingR[col-row+7] = true;

判断语句：

if( !KingCol[col] && !KingL[col+row] && !KingR[col-row+7] ){// 设置冲突域KingCol[col] = true;KingL[col+row] = true;KingR[col-row+7] = true;process( row+1 , 0 );	// 下一行判断// 恢复原状KingCol[col] = false;KingL[col+row] = false;KingR[col-row+7] = false;
}

完整代码：

#include <iostream>
#include <stdlib.h>
#include <string.h>
using namespace std;bool KingCol[8] ; 	// 	row,col处放了皇后 == KingCol[col] = true 
bool KingL[8*2];		//  == KingL[col+row] = true;
bool KingR[8*2];		//  == KingR[col-row+7] = true;int cnt = 0;void process( int row , int col ){if( col == 8 ){return ;}if( row == 8 ){cnt++;return ;}if( !KingCol[col] && !KingL[col+row] && !KingR[col-row+7] ){// 设置冲突域KingCol[col] = true;KingL[col+row] = true;KingR[col-row+7] = true;process( row+1 , 0 );	// 下一行判断// 恢复原状KingCol[col] = false;KingL[col+row] = false;KingR[col-row+7] = false;}process( row , col+1 );	// 下一列判断
}int main(){process(0,0);cout << cnt << endl;return 0;
}

结果：
输出92

嵌入式Linux工程师笔试记录 -- 2020.8.5 (四)