青少年编程知识记录 codecoming

C++中的输入与输出

注：初学者只需要掌握cin、cout即可(2.2、3.2小节)1.C++输入输出概述C++的输入输出分为两大体系：1.  C++标准输入输出流（IOStream）：以cin（输入流）、cout（输出流）为核心，属于C++原生特性，支持面向对象操作，语法简洁，无需关注数据格式细节，是C++编程中最常用的I/O方式。2.  C语言输入输出函数：以scanf（输入）、printf（输出）为核心，属于C语言标准库（stdio.h），C++完全兼容。其特点是需要手动指定数据格式，执行效
作者:亿万年的星光 分类:C++目录 浏览:

【题解】位数问题

【题目描述】

在所有的N位数中，有多少个数中有偶数个数字3？由于结果可能很大，你只需要输出这个答案对12345取余的值。

比如：在所有的2位数字，包含0个3的数有72个，包含2个3的数有1个，共73个。（请注意：1位数指1~9这9个数，不包含数字0）

【输入描述】

一个整数N（1<=N<=1000）

【输出描述】

N位数中含有偶数个数组3的个数

【样例输入】

2

【样例输出】

73
作者:亿万年的星光 分类:题解目录 浏览:

C++ 中的常量

一、说明

常量和变量是相对的概念 —— 变量是 “能变化的量”，而常量就是一旦定义就固定不变、不能修改的值。



用生活里的例子类比，你就能秒懂为什么需要常量：本质是 “给固定不变的东西贴‘只读标签’，避免误改、保证数据一致性”，没有这玩意儿，关键的固定值容易被意外修改，导致程序出错。



例子 1：身份证号（固定唯一的核心数据）



【没有常量的情况】：如果把身份证号存在普通本子上（变量），不小心写错成别人的号码，去办业务就会出错；要是多人共用这个本子，还可能被其他人随意涂改。

【有常量的情况】：把身份证号印在身份证卡片上（常量），卡片上的号码无法修改，无论谁用、什么时候用，都是同一个正确的号码 —— 这就是常量的 “不可修改性”，保证核心固定数据不被篡改。

例子 2：教室的固定座位号（不可更改的标识）



【没有常量的情况】：学生随便改座位号，上课点名时 “3 号座位” 可能坐的是 8 号同学，秩序全乱。【有常量的情况】：座位号用刻字或固定贴纸（常量），不能随意涂改，老师点 3 号座位就一定能找到对应的同学 —— 常量就是程序里 “刻死” 的固定值，不会被意外修改。

例子 3：数学中的 π（固定不变的常量）



【没有常量的情况】：每次计算都手写 3.14，有时写成 3.1415，有时写成 3.1，计算结果偏差大。

【有常量的情况】：定义一个常量 PI=3.1415926，所有计算都用这个常量，不管算多少个圆的面积，π 的值都不变，结果精准。

核心总结：



生活里的“不可修改的标签 固定标识”（身份证号、座位号、π），对应程序里的 “常量”—— 没有它们，固定不变的核心数据容易被误改，导致程序逻辑混乱、结果出错；

有了常量，能保证固定值的唯一性和不可修改性，让程序更稳定。

标签: 常量const

作者:亿万年的星光 分类:C++目录 浏览:

图论—拓扑排序

前序文章：拓扑排序 - C++目录 - 青少年编程知识记录一、简述拓扑排序是针对 有向无环图（DAG, Directed Acyclic Graph） 的一种排序算法，其核心目标是：将图中所有顶点排成一个线性序列，使得对于图中任意一条有向边 u—>v，顶点 u 都排在顶点 v 的前面。二、核心概念1.入度（In-degree）对于顶点 v，入度是指所有以 v 为终点的有向边的数量，记为in_degre

最小生成树—Prim（普里姆）算法

一、算法概述

Prim 算法是一种用于求解加权无向连通图的最小生成树（MST） 的贪心算法。它从一个顶点开始，逐步扩展生成树，每次选择连接已选顶点集和未选顶点集的最小权重边。

二、算法思想

  1. 初始化：从任意顶点开始，将其加入生成树集合

  2. 重复执行：

    • 在所有连接已选顶点和未选顶点的边中，选择权重最小的边

    • 将该边加入生成树，并将对应的未选顶点加入已选集合

  3. 终止条件：当所有顶点都加入生成树时结束

三、算法过程示例

示例图（顶点：A,B,C,D；边权重如图）：

更清晰的邻接关系（无向图，权重如图）：

  • A–B : 2

  • A–C : 4

  • A–D : 3

  • B–D : 1

  • C–D : 5

顶点集合：{A, B, C, D}

目标：用 Prim 算法找最小生成树（MST）。

每次选择连接 已选顶点集 与 未选顶点集 的最小权重边，将该边及其另一端点加入已选集合。

步骤 1

  • 已选集合 S={A}

  • 候选边（一端在 S，一端不在 S）：

    • A–B (2)   （说明:A在S中，B不在S中）

    • A–C (4)   （说明:A在S中，C不在S中）

    • A–D (3)   （说明:A在S中，D不在S中）

  • 最小权重边：A–B (2)

  • 加入 B 到 S，边 A–B 加入 MST。

MST 边：{A–B}

S = {A, B}





最小生成树—Kruskal（克鲁斯卡尔）算法

一、算法描述

在一个连通加权无向图中，找到一棵最小生成树。即，找到连接所有顶点的、权值总和最小的树，且树中不包含任何环。



二、核心思想

  1. 贪心策略：每次从未选择的边中，选取一条权值最小的边。

  2. 避免环路：如果加入这条边会导致生成树中形成环，则舍弃它。

  3. 集合管理：使用并查集数据结构来高效地判断两个顶点是否已经连通（即加入边是否会形成环）。



三、图解过程

假设我们有以下连通图 G，目标是找到它的最小生成树（MST）。

步骤 0：初始化

  • 将图中所有边按权值从小到大排序。

  • 初始化一个空的边集 MST，用于存放最小生成树的边。

  • 初始化并查集，让每个顶点自成一個集合。

排序后的边列表：(A,D):5, (C,E):5, (D,F):6, (A,B):7, (B,E):7, (B,C):8, (E,F):8, (B,D):9, ...

当前 MST： { }并查集状态： {A}, {B}, {C}, {D}, {E}, {F}