分类 C++ 下的文章

2. 计算圆的相关数据

题中给出的r、h在最后的答案中无意义

球的体积 V = 4/3 Pi r^3 球的表面积 S = 4 Pi r^2

体积公式推导和论证 : https://www.zhihu.com/question/405287938

#include <iostream>
#include <iomanip>

using namespace std;

const float PI = 3.1415926;

int main(){

    float r,h;

    cout << "请依次输入半径和圆柱体高度." << endl;
    cin >> r >> h;

//  cout << setpreise(2) << setfixed;
    cout << setiosflags( ios::fixed ) << setiosflags( ios::right ) << setprecission( 2 );
    cout << "\n周长:" << 2*PI*r;
    cout << "\n面积:" << PI*r*r;
    cout << "\n圆球表面积:" << 4 * PI * r * r;
    cout << "\n球的体积:" << 4.0 / 3.0 * PI * r * r *r;
    cout << "\n圆柱体体积:" << PI*r*r*h;
    cout << endl;
    return 0;
}

3. 转换温度单位

#include <iostream>
#include <iomanip>

using namespace std;

int main(){

    float t;

    cout << "请输入华氏温度:" << endl;
    cin >> t;

    cout << setiosflags( ios::fixed ) << setiosflags( ios::left ) << setprecision( 2 );
    cout << "\n摄氏温度是:" << 5.0 / 9.0 * ( t - 32 ) ;
    cout << endl;
    return 0;
}

4.

(1) 要定义为char,cout输出int类型的时候会直接输出数字。

(2) 可以输出 (int) ( c1 - 0 ) 或者 (int) c1 , (int)c2

5. int 和 char 是否等价

否 最基本的 char ∈ int char1个字节、int 2-4个字节

其他等等………………

- 阅读剩余部分 -

隐约记得之前做过一个c++的题目是判断一个数是否素数(质数) 我当时给的算法是判断 2 - x/2, 因为被除数大于 x/2 那商一定小于2,所以被除数必须大于x/2

最近看书的时候发现通用的算法是计算 2- sqrt(x) 即 根号x 这就让我产生疑问了,毋庸置疑,这个算法的效率更高,时间复杂度是logn。 那为什么到sqrt(x)就够了呢?

我反复思考总算得出了结论,这里用反证法即可:

已知 n 不是素数,且a,b是 n的两个根, a*b = n
假设 b>sqrt(n),且a>=sqrt(n)
则a*b > sqrt(n) * sqrt(n) 即 a*b > n 与条件相悖

得出若存在一个根大于sqrt(n),
那必定存在另一个小于sqrt(n)的根

与此对应的逆否命题是

若不存在小于sqrt(n)的根,则不存在大于sqrt(n)的根

根据这个证明的结论,判断是否是素数,最多只需要判断到 n 的平方根即可。

1. 使用前需要导入库

C和C++语言层面都是不提供输入输出功能的。 C使用scanf和printf这类函数用于输入输出 C++使用iostream库中的 cin、cout来进行输入输出

使用cin 导入 #include <istream> 使用cout 导入 #include <ostream> 都使用 导入 #include <iostream>

2. 输入输出流可以连续使用表达式

cin >> a >> b >> c; cout << a << b << c << endl;

3. 输入输出流自动根据上下文处理变量类型

4. 输出流 支持使用表达式

cout << a+'b' << endl;

5. cin会根据变量的类型提取相应长度的字节

空格起到分隔符的作用

char c1,c2;
int a;
float b;

cin >> c1 >> c2 >> a >> b;
1234 56.78

1,2会被当做char 赋值给c1、c2 34赋值给a 56.78赋值给b

6. 获取带有空格内容的String 需要使用getline()

#include <iostream>
#include <string>

int main{
    string a;

    getline( cin, a );
    cout << a << endl;
    return 0;
}

7. 输入输出流中的控制符

需要导入 <iomanip>

dec 默认 10进制 hex 16进制 oct 8进制

double a = 155330000.001;

setfill( c ) 空白位置自动填充 char
setw(n) 设定宽度( 简单理解为 在屏幕上占几个格子 )

setprecision(n) 设定浮点数精度 **默认6位**

setiosflags( iosflag ) 设定格式

    ios::fixed          固定小数位表示         155330000.001000
    ios::scientific     指数形式表示          1.553300e+08
    ios::left           左对齐
    ios::right          右对齐
    ios::skipws         跳过开头的空格
    ios::uppercase      转大写
    ios::lowercase      转小写
    ios::showpos        显示数字正号          +1.5533e+08

#include <iostream>
using namespace std;

int main()
{
    char c1,c2,c3,c4,c5;
    c1='C', c2='h', c3='i', c4='n', c5='a';
    c1+=4,  c2+=4,  c3+=4,  c4+=4,  c5+=4;
    cout << c1 << c2 << c3 << c4 << c5 << endl;
   return 0;
}

这里可以考虑将某个特定数字改写为常量、或变量

在C、C++中有一系列位运算符,在学习位运算符的时候就需要先了解反码、补码的原理。 因为位运算是按照变量在内存中所表示来进行运算的。

而计算机中,数字是按照二进制的补码进行存储的,当然(其他类型以及高级类型本质上也是数字)

二进制的原码,就是将十进制数转换为二进制。

正数的 反码、补码和原码一致

负数的 反码、补码按照以下方式转换

反码:原码符号位不变,其他位按位取反就可以得到了。 补码:反码+1就得到补码。

int a = 251
int b = -232

a的原码:00000000 11111011 a的反码:00000000 11111011 a的补码:00000000 11111011

b的反码:11111111 00010111 b的原码:10000000 11101000 b的补码:11111111 00011000

a+b = 19

使用ab的原码相加 得 10000001 11100011 即 -483 使用ab的反码相加 得 00000000 00010010 即 18 使用ab的补码相加 得 00000000 00010011 即 19

使用补码,如果从比较粗浅的角度来理解,主要是因为负数存在一个 -0,这个 -0 和“正数”中的0 冲突了,在进行加法运算的时候,-0也占了一个位置,这样就会导致,正负数相加结果和我们数学体系中的表示结果差一位,所以负数一律补1,这样就规避掉-0这个陷阱了。

“这个问题理解的时候,我觉得不要讲计算机中的数字理解位数字,实际上计算机里没有所谓的正负,只是存在了2^n中状态,而我们人类数学刚好存在一个0点,这个0点在二进制表示中,其实不应该有位置,但是又必须有,所以就会导致另外一个对称状态很尴尬。”


回到位运算

<< 左移 int a = 5; a<<=1 0000 0101->0000 1010 a=10

>> 右移 int a = 5; a>>=1; 0000 0101->0000 0010 a=2

& 与(且) int a = 5; a&=1; 0000 0101 & 0000 0001 > 0000 0001 a=1

int a = 5; a&=3; 0000 0101 & 0000 0011 > 0000 0001 a=1

|int a = 5; a|=1; 0000 0101 | 0000 0001 > 0000 0101 a=5

int a = 5; a|=3; 0000 0101 | 0000 0011 > 0000 0111 a=7

^ 异或 (不同) int a = 5; a^=1; 0000 0101 ^ 0000 0001 > 0000 0100 a=4

int a = 5; a^=3; 0000 0101 ^ 0000 0011 > 0000 0110 a=6

~ 取反 单目运算 int a = 5; ~0000 0101 > 1111 1010 (补码) 对补码进行还原 反码= 1111 1001,得到原码 = 1000 0110a= -6

C++中的基本数据类型定义没有最终的规定,由编译系统自行确定。

但是一些关系已经确定

长整形 不小于整形

短整形 不大于整形

一般16位机C++系统中,short int,int 2个字节,long int 4个字节 VC++中,short 2个字节,int,long int 4个字节

一个字节是计算机中的8个bit位 一个比特位就是硬件中的一个逻辑单元 可以表示0 或者1 所以一个字节就是 00000000 一个字节最大值就是 11111111 换算成10进制就是 1+2+4+8+16+32+64+128 = 255

两个字节就是 00000000 00000000 最大值是 11111111 11111111 => 1+2+... 2^15 = 65535

这里另外需要考虑一个问题就是符号,如果将刚才的范围的第一个比特位用作符号表示的话,那么一个字节的范围就是 1 0000000 - 1 11111110 0000000 - 0 1111111-128 -> -1,0 -> 127

这里的负数比正数多一个原因在于 补码机制

无符号,有符号 位数一致,无符号 绝对值大一倍(但没有负数)

基本关系: boolean = char < short <= int <= long <= float < double

Bool实际上需要的是最少的,只需要0,1但是最低的位数也是1字节 char也是1字节 255的范围用于表示基本英文字母和基础符号足够了

浮点数在计算机的表示方法

loat规格float共计32位,4字节由最高到最低位分别是第31、30、29、……、0位,则:31位是符号位,1表示该数为负,0表示为正。30-23位,一共8位是指数位。22-0位,一共23位是尾数位。3、转换例子按照IEEE浮点数表示法,将float型浮点数123456.0f转换为二进制(注:这里的f表示浮点数,为十进制数,不是表示16十六进制)。处理不带小数的浮点数时,直接将整数部转化为二进制表示:11110001001000000也可以这样表示:11110001001000000.0然后将小数点向左移,一直移到离最高位只有1位:1.11100010010000000共左移了16位,所以原数就等于:1.11100010010000000*(2^16)。

其实简单来说浮点数就是三个部分,位数0、小数点位置(二进制) 1-8 、整体数值二进制表示 9-31

谭浩强 C++程序设计(第三版)P189 第16题

输入一个字符串,内有数字和非数字字符,如

a123x456_17960?302tab5876

将其中连续的数字作为一个整数,依次存放到一个数组a中。统计总共有多少个整数,并输出这些数。

这个问题是比较好解决的,主要是三步

  1. 开辟一个 int a[(n+1)/2]; 大小的整数数组a,(n+1)/2 是字符串中能够包含的至多个整数了。 初始化一个数字统计 int total = 0;,用来累计出现过的数字总数。

  2. 遍历字符串,比对是否是数字,如果是 压入栈中,如果不是,将栈逐步清空并将取出的若干个数字计算为十进制数,其中每次出栈,将进制+1,则可以顺利求出。 每次得出一个新整数,total++

  3. 以total为终,遍历a并输出。

#include <iostream>
#include <stack>

using namespacing std;

int getNumberFromStack( stack &s ){ // 传递引用

    int level = 1;
    int number= 0;

    while( !stack.empty() ){

        number += stack.top() * level;

        stack.pop();
        level *= 10;
    }
    return number;
}

int main(){

    string s;
    cout << "请输入一个字符串,如a123x456_17960?302tab5876。\n";
    cin >> s;

    int a[ (s.size() + 1)/2 ];
    int total = 0;
    stack<int> numberStack;

    for( unsigned int i =0; i< s.size(); i++ ){

        if( s[i]<='9' && s[i]>='0' ){

            numberStack.push( s[i]-0 );
        }else if( !numberStack.empty() ){

            a[total++] = getNumberFromStack( numberStack );
        }
    }

    // 输出全部数字
    for( int k=0; k < total; k++ ){

        cout << a[k] << "\n";
    }

    return 0;
}



数据结构、算法与应用 习题6.1 69题 p143

给出一种整数表示法,用于对任意大小的整数进行数学运算(加减乘除),且不能有精度损失。

这里应该能支持两种表示法,1链表,2数组。

使用链表比较符合我们直观上对于数字的印象,其中将 rear链接到最后一位数,那么使用prev就可以陆续的取出每一个数字。 并且在进行数学运算时,我们无需关注最终的位数,只需要将结果insert进入结果链表中即可。

由于没有规定一定是正整数,所以需要给一个符号。 (在网上也搜索了一些大数运算的参考,没有提供有符号运算的版本) 带符号的时候,逻辑会变复杂不少。

这里我给出一个带符号的方式 其中isNegative true为负数,false为正数

为了表示符号对于运算的影响,我会写两个版本的 加法

链表表示:


class BigInt: public Chain<int>{
public:
    bool isNegative = false;

    BigInt( int* a, int size ){ // 基于数组构造
        for( int i=0; i<size; i++ ){
            insert( a[i] );
        }
    }

    // 最基本的 正正 相加
    BigInt& operator+( BigInt& bigInt ){
        int plus = 0;  // 进位
        int res  = 0;  // 单次计算结果
        BigInt result = new BigInt; // 结果
        ChainNode<int>* cursor = last();
        ChainNode<int>* targetCursor = bigInt.last();

        // 使用倒序的方式取出元素并计算
        while( cursor->prev() && targetCursor->prev() ){
            res = cursor->element + targetCursor->element + plus;
            plus = res > 9 ? 1 : 0;

            result->prepend( res ); // prepend即为 addAfter( head )
            cursor = cursor->prev();
            targetCursor = targetCursor->prev();
        }
        while( cursor->prev() ){
            result->prepend( cursor->element );
            cursor = cursor->prev();
        }
        while( targetCursor->prev() ){
            result->prepend( targetCursor->element );
            targetCursor = targetCursor->prev();
        }
        return result;
    }

    // 完整版 带符号运算的加法 (不是重载!!!)
    BigInt& operator+( BigInt& bigInt ){

        BigInt result = new BigInt; // 结果
        result.isNegative = size() >= bigInt.size() ? isNegative : bigInt.isNegative; // 暂定为较大位数。 如果位数相同,根据最后一次计算结果修正。

        int plus = 0;   // 进位或借位
        int res;        // 单次计算结果
        ChainNode<int>* cursor = last();                // 当前游标
        ChainNode<int>* targetCursor = bigInt.last();   // 目标游标

        while( cursor->prev() && targetCursor->prev() ){

            res = isNegative ? -cursor->element : cursor->element
                + bigInt.isNegative ? -targetCursor->element : targetCursor->element
                + plus; // 我们把大数中的每一个数 都当成 a[i] * 10i来看。
            // 绝对值超过>9的都需要向上进一位(一定是同符号)
            // 不同符号 结果小于0的 需要借位
            // 同符号小于0,不同符号大于0小于10的都可以忽略
            // 小于0的时候 res需要取绝对值,保持元素的非负

            if( res >9 || res<-9 ){
                plus = 1;
            }else if( res < 0 ){
                plus = isNegative == bigInt.isNegative ? 0 : -1;
                res  = -res;
            }

            result.prepend(res);
        }

        if( size() == bigInt.size()  ){ // 修复位数相同的问题
            if( plus>0 ){
                result.prepend(1); // 一定是同符号的,直接+1
            }else if( plus<0 ){
                result.isNegative = true; // 此时已经无法借位了,确认最终结果为负数
            }
        }

        // 任意链表仍有元素未计算,继续补齐
        while( cursor->prev() ){
            result->prepend( cursor->element + plus );
            plus = 0;
            cursor = cursor->prev();
        }
        while( targetCursor->prev() ){
            result->prepend( targetCursor->element + plus );
            plus = 0;
            targetCursor = targetCursor->prev();
        }

        // 修复首位为0的情况 // 全部删除则为空 即0
        while( result.first().element == 0 ){
            result.remove( result.first() );
        }

        return result;
    }

    // 在有符号加法的前提下,减法运算就简单多了
    BigInt& operator-( BigInt& bigInt ){

        bigInt.isNegative = !bigInt.isNegative; // 符号位颠倒
        BigInt result = *this + bigInt;

        bigInt.isNegative = !bigInt.isNegative; // 恢复
        return result;
    }
}

本页的练习在无特殊说明时一律按照 单右向循环 链表为准。

1. L=(a,b,c,d,e) 作图 pass

2. setSize

复杂度O(n)
template <class T>
void chain<T>::theSize( int n ){
    chainNode<T> current = firstNode();
    int i=0, max = _size < n ? _size : n;

    // 由于不是双向链表,所以需要先到达n的极点
    while( i < max ){
        current = current->next();
        i++;
    }

    chainNode<T> tmp;
    // 如果有多余的
    while( _size > n ){
        tmp = current->next();
        delete current; // 系统会执行element析构
        current = tmp;
    }

    _size = n;
}

3. set()

复杂度O(n) 在实际使用的时候,链表一般不用index表示法来获取或设置元素。因为每次都相当于O(n)的复杂度。

template <class T>
void chain<T>::checkIndex( int theIndex ){

    if( theIndex <0 || theIndex >= _size ){
        throw illegalIndex("Out of range");
    }
}

template <class T>
void chain<T>::set( int theIndex, T& theElement ){
    checkIndex(theIndex);
    chainNode<T>* current = firstNode();
    int i = 0;
    while( i < _size ){
        current = current->next();
    }
    current->element.~T(); // 析构
    current->element = theElement;
}

4. removeRange

复杂度O(n) 和上面的setSize类似,做一次遍历,之后将切割掉的部分接起来即可。

template <class T>
void chain<T>::setSize( int fromIndex, int toIndex ){
    checkIndex(fromIndex);
    checkIndex(toIndex);

    chainNode<T>* current = firstNode();
    int i=0;

    // fromIndex的极点
    while( i < fromIndex ){
        current = current->next();
        i++;
    }

    chainNode<T>* tmp;

    while( i < toIndex ){
        tmp = current->next();
        delete current; // 系统会执行element析构
        current = tmp;
    }

    _size -= toIndex-fromIndex +1; // 考虑左右闭区间
}

5. lastIndex()

复杂度O(n) 遍历元素并比对,不即时返回。

template <class T>
int chain<T>::lastIndex( T& theElement ) const{

    if( empty() ) return -1;

    chainNode<T>* current = firstNode();
    int i = 0, lastIndex = -1;

    while( i< _size ){
        if( current->element == theElement ){
            lastIndex = i;
        }
        current = current->next();
        i++;
    }
    return lastIndex;
}

6. 重载[]

复杂度O(n) 实际上重载应该包含两种,分别是提供左值,右值返回。

template <class T>
const T& chain<T>::operator[](int n) const{  } // 右值
T& chain<T>::operator[]( int n) const{ // 左值
    int i = 0;
    chainNode<T>* current = firstNode();

    while( i < n ){
        current = current->next();
    }
    return current->element;
}

7. 重载==

复杂度O(n) 同步遍历两个链表元素,一旦发现不同元素返回false。

template <class T>
bool chain<T>::operator==( chain<T>& c) const{

    if( size() != c.size() ) return false;
    chainNode<T>* current = firstNode();
    chainNode<T>* target  = c.firstNode();

    int i = 0;
    while( i < size() ){
        if( current->element !== target->element ) return false;
        current = current->next();
        target  = target->next();
    }
    return true;
}

8. 重载!=

复杂度O(n)

template <class T>
bool chain<T>::operator!=( chain<T>& c) const{
    return !*this == c;
}

9. 重载<

复杂度O(n) 略微需要注意的是,除了最后一项的值完全相等以外,其他的相等 都不能判断非<。 所以在遍历的靠前阶段,== 都应该算成功,只有最后一项相等判断非小于。

template <class T>
bool chain<T>::operator<( chain<T>& c) const{

    if( size() > c.size() ) return false;
    chainNode<T>* current = firstNode();
    chainNode<T>* target  = c.firstNode();

    int i = 0;
    while( i < size() ){
        if( current->element > target->element ){
            return false;
        }else{
            current = current->next();
            target  = target->next();
        }
    }
    if( current->element == target->element ) return false;
    return true;
}

- 阅读剩余部分 -

1### 2. L = (a,b,c,d,e) ... 做图

初始状态:

0 1 2 3 4 5 6 7 8 9
a b c d e  

insert(0,f)

0 1 2 3 4 5 6 7 8 9
f a b c d e  

insert(3,g)

0 1 2 3 4 5 6 7 8 9
f a b g c d e  

insert(7,h)

0 1 2 3 4 5 6 7 8 9
f a b g c d e h  

earse(0)

0 1 2 3 4 5 6 7 8 9
a b g c d e h  

erase(4)

0 1 2 3 4 5 6 7 8 9
a b g c e h  

3. changeLength2D

二维数组的话要基于Array设计一个矩阵类,其中的每一行都是一个Array对象。

template <class T>
class ArrayMatrix: public Array{
    void changeLength2D( int x, int len );
}

template <class T>
void ArrayMatrix::changeLength2D( int rowIndex, int len ){
    checkIndex(x);
    get(rowIndex).changeLength(len);
}

3. 构造函数

好像题目描述有问题。 我自己写的是提供一个是否自动扩容的参数。如果配置为不自动扩容则在超出的时候抛出异常。

enum class ARRAY_AUTO_CAPACITY
{
    DISABLED = 0,ENABLED = 1
};

template <class T>
class Array{
public:
    Array(int initCapacity = ARRAY_DEFAULT_CAPACITY, ARRAY_AUTO_CAPACITY autoCapacity = ARRAY_AUTO_CAPACITY::DISABLED);
    void checkMax();
private:
    ARRAY_AUTO_CAPACITY _autoCapacity =  ARRAY_AUTO_CAPACITY::DISABLED;
}


template<class T>
inline void Array<T>::checkMax()
{
    if (_size >= _capacity) {

        switch (_autoCapcity)
        {
        case ARRAY_AUTO_CAPACITY::ENABLED:
            changeCapacityTo(_capacity << 1);
            break;
        case ARRAY_AUTO_CAPACITY::DISABLED:
            throw illegalInputData("Array is full.");
            break;
        default:
            break;
        }
    }
}

5. trimToSize()

实际上就是改变数组长度, 长度为size或1。 这里我基于我改写的 changeCapacityTo()来实现,实际上是一回事。

复杂度是O(n)

void trimToSize(){
    changeCapacityTo( _size>0 ? _size : 1 );
}

template<class T>
inline void Array<T>::changeCapacityTo(int newCapacity)
{
    T* newElements = new T[newCapacity];
    _capacity = newCapacity;
    _size = newCapacity < _size ? newCapacity : _size;

    for (int i = 0; i < _size; i++)
    {
        newElements[i] = _elements[i];
    }
    delete[] _elements;

    _elements = newElements;
}

6. setSize

这一题,同样题目描述是有问题的。 见上一题changeCapacityTo()

7. 重载[]

T& operator[]( int n){
    checkIndex(n);
    return _elements[n];
}

8. 重载==

template<class T>
bool operator==( const Array<T>& targetArray ) const{
    if( size()!= targetArray.size() ){
        return false;
    }
    for( int i=0; i<size();i++ ){
        if( get(i) != target.get(i) ){
            return false;
        }
    }
    return true;
}

9. 重载!=

template<class T>
bool operator!=( const Array<T>& targetArray ){
    return !*this == targetArray;
}

10. 重载<

见8 . 其中!= 替换为>

- 阅读剩余部分 -