迎战中考-怎样给电脑设密码
.
.
1.
时针分针重合几次
表面上有
60
个小格,每小格代表一分钟,
时针每分钟走
1/12
小格,分针每分钟走
1
小格,从第一次重合到第二次重合分
针比时针 多走一圈即
60
小格,所以
60/
(
1-1/12
)
=720/11
每隔
720/11
分才重合一次(而并不是每小时重合一次)
< br>1440
里有
22
个
720/11
,
如果说算上0
点和
24
点,
那也是重合
23
次而已,
但我
觉得
0
点应该算到前一天的
24
点头上,所以每一天循环下来重合< br>22
次啊
2.
找出字符串的最长不重复子串,输出长度
建一个
256
个单元的数 组,
每一个单元代表一个字符,
数组中保存上次该字符上
次出现的位置;
依次读入字符串,同时维护数组的值;
如果遇到冲突了,
就返回冲突字符中 保存的位置,
继续第二步。
也可以用
hashmap
保存已经出现的字符和字 符的位置
3.
说是有一个文本文件,大约有一万行,每行一个词,要求统计出其中最频繁
出
现的前十个词。
先用哈希,
统计每个词出现的次数,
然后在用在< br>N
个数中找出前
K
大个数的方法
找出出现
. .
. .
.
.
次数最多的前
10
个词。
4.
如题
3
,但是车次文件特别大,没有办法一次读入存。
1)
直接排序,写文件时,同时写入字符串及其出现
次数。
2) < br>可以用哈希,比如先根据字符串的第一个字符将字符串换分为多个区域,每
个区域的字符串写到一 个文件,
然后再用哈希
+
堆统计每个区域前
10
个频率最高
的字符串,最后求出所有字符串中前
10
个频率最高的字符串。
5.
有一个整数
n
,将
n
分解成若干个整数之和,问如何 分解能使这些数的乘积
最大,输出这个乘积
m
。例如:
n=12
(
1
)分解为
1+1+1+…+1,
12
个
1, m=1*1*1……*1=1
(
2
)分解为
2+2+…+2,6
个
2
,
m=64
(
3
)分解为
3+3+3+3
,
4
个
3
,
m=81
(
4
)大于等于
4
时分解时只能分解为
2
和
3
,且
2
最多两个
f(n) = 3*f(n-3) n>4
f(4) = 2*2
f(3) = 3
f(2) = 2
分解为
4+4+4
,
3
个
4
,
m=64
6.
求数组
n
中出现次数超过一半的数
. .
. .
.
.
把数组分成
[n /2]
组,则至少有一组包含重复的数,因为如果无重复数,则最多
只有出现次数等于一半的数 。算法如下:
k<-n;
while k>3 do
把数组分成
[k/2]
组
;
for i=1 to [k/2] do
if
组
2
个数相同,则任取一个数留下
;
else 2
个数同时扔掉
;
k<-
剩下的数
if k=3
then
任取
2
个数进行比较
;
if
两个数不同,则
2
个数都扔掉
else
任取一个数
if k=2 or 1 then
任取一数
7. A
文件中最多有
n
个正整数,而且每个数均小于
n
,
n <=10
的七次方。不会
出现重复的数。
要求对
A
文件中 的数进行排序,可用存为
1M
,磁盘可用空间足够。
不要把任何问题都往很 复杂的算法上靠,
最直接最简单的解决问题才是工程师应
有的素质,
题目给 的很有分寸:
n
个数,
都小于
n
,
两两不同,
1M =10^6byte=10^7bit
的存,
n <10^7
. .
. .
.
.
思路:
把
1M
存看作 是一个长度为
10^7
的位数组,每一位都初始化为
0
从头扫描
n
个数,如果碰到
i
,就把位数组的第
i
个位置置为
1
,
1M
存有点少,
(
1M = 8M bits),
可以代表
8M
整数,现在
n <=10
的七次方,< br>你可以读
2
遍文件,
就可以完成排序了。
第一次排
n
<8M
得数,
第
2
遍排
8M<=
div=
8.
有
10
亿个杂乱无章 的数,怎样最快地求出其中前
1000
大的数。
1)
建一个
1000
个数的堆,复杂度为
N*(log1000)=10N
2) 1.
用每一个
BIT
标识一个整数的存在与否,这样一个字节可以标识
8
个整数
的存在与否,对于所有
32
位的整数,需要
512 Mb
,所以开辟一个
512Mb
的字符
数组
A
,初始全0
2.
依次读取每个数
n
,将
A[n >>3]
设置为
A[n>>3]|(1<<=
style=
3.
在
A
中,从大到小读取
1000
个值为
1< br>的数,就是最大的
1000
个数了。
这样读文件就只需要
1
遍,
在不考虑存开销的情况下,
应该是速度最快的方法了。
9.
一棵树节点
1, 2, 3, ... , n.
怎样实现:
先进行
O(n)
预处理,然后任给两个节点,用
O(1)
判断它们的父子关系
dfs
一遍,记录每个结点的开始访问时间
Si
和结束访问时间
Ei
. .
. .
.
.
对于两个节点
i ,j
,若区间
[Si,Ei]
包含
[Sj,Ej]
,则
i< br>是
j
的祖先。给每个节点
哈夫曼编码也行,但只适合一般的二叉树,而实际问题 未必是
Binary
的,所以
编码有局限性
10. < br>给定一个二叉树,求其中
N
(
N>=2
)个节点的最近公共祖先节点。 每个节点
只有左右孩
子指
针,没有父指针。
后序递归给每个节点打分,
每个节点的分数
=
左分数
+
右分数
+k
,
如果某孩子是给
定节点则
+1
最深的得分为
N< br>的节点就是所求吧,
细节上应该不用递归结束就可以得到这个节
点
11.
如何打印如下的螺旋队列:
21 22
。。。。
20 7 8 9 10
19 6 1 2 11
18 5 4 3 12
17 16 15 14 13
#include
#define max(a,b) ((a)<(b)?(b):(a))
. .
. .
.
.
#define abs(a) ((a)>0?(a):-(a))
int foo(int x, int y)
{
int t = max(abs(x), abs(y));
int u = t + t;
int v = u - 1;
v = v * v + u;
if (x == -t)
v += u + t - y;
else if (y == -t)
v += 3 * u + x - t;
else if (y == t )
v += t - x;
else
v += y - t;
return v;
}
int main()
{
int x, y;
for (y=-2;y<=2;y++)
{
. .
. .
.
.
for (x=-2;x<=2;x++)
printf(
printf(
}
return 0;
}
第
0
层规定为中间的那个
1
,第
1
层为
2
到
9
,第
2
层为
10
到
25
,……
好像看出一点名堂来了?注意到
1
、
9
、25
、……不就是平方数吗?而且是连续
奇数(
1
、
3
、
5
、……)的平方数。这些数还跟层数相关,推算一下就可以知道
第
t
层之一共有
(2t-1)^2
个数,因而第
t
层会从
[(2t-1)^2]
+
1
开始继续
往外螺旋。给定坐标
(x,y)
,如何知道该点处于第几层?
so easy
,层数
t =
max(|x|,|y|)
。
知道了层数,接下来就好办多了,这时我们就知道所求的那点一定在第
t
层这个圈上,
顺着往下数就是了。
要注意的就是螺旋队列数值增长方向和坐标轴正方
向 并不一定相同。我们可以分成四种情况——上、下、左、右——或者——东、
南、西、北,分别处于四条 边上来分析。
东
|
右:
x == t
,队列增长方向和
y
轴一致,正向(
y = 0
)数值为
(2t-1)^2 +
t
,所以
v = (2t-1)^2 + t + y
. .
. .
.
.
南
|
下:
y
==
t
,
队列增长方向和
x
轴相反,
正南方向
(
x
=
0
)
数值为
(2t-1)^2
+ 3t
,所以
v
=
(2t-1)^2 + 3t - x
西
|
左:
x
==
-t
,
队列增长方向和
y
轴相反,
正西方向
(
y
=
0
)
数值为
(2t-1)^2
+ 5t
,所以
v = (2t-1)^2 + 5t - y
北
|
上:
y
==
-t
,
队列增长方向和
x
轴一致,
正北方向
(
x
=
0
)
数值为
(2t-1)^2
+ 7t
,所以
v
=
(2t-1)^2 + 7t + x
12.
一个整数,
知道位数,
如何判断它是否能被
3
整除,
不可以使用除法和模运算
首先
3x=2^n+1
时
仅当
n
为奇数才可能
因为
2^n = 3x + (-1)^n;
所以该问题
就转化为了
找到最后一个为
1
的位
a
,看看向前的一个
1
(
b
)和这个位的距离,如果为 偶数
的距离则不能整除,如果是奇数,去除
b
之后的位继续判断
13. seq=[a,b,...,z,aa,ab,...,az,ba,bb...,bz,.. .za,zb,...,zz,aaa...],
求
[a-z]+(
从
a到
z
任意字符组成的字符串
)s
在
seq
的位置,即排 在第几
本质就是
26
进制。
大家都知道,< br>看一个数是否能被
2
整除只需要看它的个位能否被
2
整除即可。
可
是你想过为什么吗?这是因为
10
能被
2
整除,因此一个数10a+b
能被
2
整除当
. .
. .
.
.
且仅当
b
能被
2
整除。
大家也知道,
看 一个数能否被
3
整除只需要看各位数之和
是否能被
3
整除。这又是为 什么呢?答案或多或少有些类似:因为
10^n-1
总能
被
3
整除。
2345
可以写成
2*(999+1) + 3*(99+1) + 4*(9+1) + 5
,展开就是
2*999+3*99+4*9
+
2+3+4+5。前面带了数字
9
的项肯定都能被
3
整除了,于是要
看
2345
能否被
3
整除就只需要看
2+3+4+5
能否被
3
整除了。当然,这种技巧只
能在
10
进制下使用,不过类似的结论可以推广到 任意进制。
注意到
36
是< br>4
的整数倍,而
ZZZ...ZZ
除以
7
总是得
55 5...55
。也就
是说,
判断一个
36
进制数能否被
4< br>整除只需要看它的个位,
而一个
36
进制数能
被
7
整 除当且仅当各位数之和能被
7
整除。
如果一个数同时能被
4
和
7
整除,
那
么这个数就一定能被
28
整除。于是问题转化为,有多 少个连续句子满足各位数
字和是
7
的倍数,同时最后一个数是
4
的倍 数。这样,我们得到了一个
O(n)
的
算法:用
P[i]
表示前若干 个句子除以
7
的余数为
i
有多少种情况,扫描整篇文
章并不断更新< br>P
数组。
当某句话的最后一个字能被
4
整除时,
假设以这句话 结尾
的前缀和除以
7
余
x
,
则将此时
P[x]的值累加到最后的输出结果中
(两个前缀的
数字和除以
7
余数相同,则较 长的前缀多出来的部分一定整除
7
)。
上述算法是我出这道题的本意,
但比赛后我见到了其它各种各样新奇的
算法。比如有人 注意到
36^n mod 28
总是等于
8
,利用这个性质也可以构造出类< br>似的线性算法来。还有人用动态规划(或者说递推)完美地解决了这个问题。我
们用
f[ i,j]
表示以句子
i
结束,除以
28
余数为
j
的 文本片段有多少个;处理下
一句话时我们需要对每一个不同的
j
进行一次扫描,把f[i-1,j]
加进对应的
f[i,j']
中。
最后输出所有的
f[i,0]
的总和即可。
这个动态规划可以用滚动数组,
因此它的空间同前面的算 法一样也是常数的。
. .
. .
.
.
如果你完全不知道我在说什么,
你可以看看和进位制、同余相关的文章。
另外,我之前还曾出过一道很类似的题
(VOJ1090)
,你 可以对比着看一看。
有一 个整数
n,
写一个函数
f(n),
返回
0
到
n之间出现的
的个数。
比如
f(13)=6,
现在
f(1 )=1,
问有哪些
n
能满足
f(n)=n
?
例如:
f(13)=6,
因为
1,2,3,4,5,6,7,8,9,10 ,11,12,13.
数数
1
的个数,正好是
6.
public class Test {
public int n = 2;
public int count = 0;
public void BigestNumber(int num) {
for (int i = 1; i <= num; i++) {
int m = 0;
. .
. .
.
.
int j = i;
while (j > 0) {
m = j % 10;
if (m == 1)
count++;
if (j > 0)
j = j / 10;
}
}
n(
}
public static void main(String args[]) {
Test t = new Test();
long begin = tTimeMillis();
. .
. .
.
.
Number(10000000);
long end = tTimeMillis();
n(
总时间
秒
}
}
结果:
f(10000000)=7000001
总时间
5
秒
1
、将一整数逆序后放入一数组中(要求递归实现)
void convert(int *result, int n) {
if(n>=10)
convert(result+1, n/10);
*result = n%10;
}
int main(int argc, char* argv[]) {
int n = 123456789, result[20]={};
convert(result, n);
. .
. .
.
.
printf(
for(int i=0; i<9; i++)
printf(
}
2
、求高于平均分的学生学号及成绩(学号和成绩人工输入)
double find(int total, int n) {
int number, score,
average;
scanf(
if(number != 0) {
scanf(
average = find(total+score, n+1);
if(score >= average)
printf(
return average;
} else {
printf(
return total/n;
}
}
int main(int argc, char* argv[]) {
find(0, 0);
}
. .
. .
.
.
3
、递归实现回文判断(如:
abcdedbca
就是回文,判断一个面试者对递归理解
的简单程序)
int find(char *str, int n) {
if(n<=1) return 1;
else if(str[0]==str[n-1]) return find(str+1, n-2);
else
return 0;
}
int main(int argc, char* argv[]) {
char *str =
printf(
}
4、组合问题(从
M
个不同字符中任取
N
个字符的所有组合)
void find(char *source, char *result, int n) {
if(n==1) {
while(*source)
printf(
} else {
int i, j;
for(i=0; source != 0; i++);
for(j=0; result[j] != 0; j++);
for(; i>=n; i--) {
result[j] = *source++;
. .
. .
.
.
result[j+1] = '0';
find(source, result, n-1);
}
}
}
int main(int argc, char* argv[]) {
int const n = 3;
char *source =
if(n>0 && strlen(source)>0 && n<=strlen(source))
find(source, result, 3);
}
5
、分解成质因数
(
如
43 5234=251*17*17*3*2
,据说是华为笔试题
)
void prim(int m, int n) {
if(m>n) {
while(m%n != 0) n++;
m /= n;
prim(m, n);
printf(
}
}
int main(int argc, char* argv[]) {
int n = 435234;
. .
. .
.
.
printf(
prim(n, 2);
}
6
、
寻找迷宫的一条出路,
o
:
通路;
X
:
障碍。
(大家经常谈到的一个小算法题)
#define MAX_SIZE
8
int H[4] = {0, 1, 0, -1};
int V[4] = {-1, 0, 1, 0};
char Maze[MAX_SIZE][MAX_SIZE] = {{'X','X','X','X','X','X','X','X'},
{'o','o','o','o','o
','X','X','X'},
{'X','o','X','X','o
','o','o','X'},
{'X','o','X','X','o','X',
'X','o'},
{'X','o','X','X','X','X','X','X
'},
{'X','o','X','X','o','o','o','X'},
{'X','o','o','o','o','X','o','o'},
{'X','X','X','X','X
','X','X','X'}};
void FindPath(int X, int Y) {
if(X == MAX_SIZE || Y == MAX_SIZE) {
. .
. .
.
.
for(int i = 0; i < MAX_SIZE; i++)
for(int j = 0; j < MAX_SIZE; j++)
printf(
' : 'n');
}else for(int k = 0; k < 4; k++)
if(X >= 0 && Y >= 0 && Y < MAX_SIZE && X < MAX_SIZE && 'o' == Maze[X][Y])
{
Maze[X][Y] = ' ';
FindPath(X+V[k], Y+H[k]);
Maze[X][Y] ='o';
}
}
int main(int argc, char* argv[]) {
FindPath(1,0);
}
7
、随机分配座位,共
50< br>个学生,使学号相邻的同学座位不能相邻
(
早些时候用
C#
写的,没有 用
C
改写)。
static void Main(string[] args)
{
int Tmp = 0, Count = 50;
int[] Seats = new int[Count];
bool[] Students = new bool[Count];
. .
. .
.
.
RandStudent=new ();
Students[Seats[0]=(0,Count)]=true;
for(int i = 1; i < Count; ) {
Tmp=(int)(0,Count);
if((!Students[Tmp])&&(Seats[i-1]-Tmp!=1) && (Seats[i-1] -
Tmp) != -1) {
Seats[i++] = Tmp;
Students[Tmp] = true;
}
}
foreach(int Student in Seats)
(Student +
();
}
8
、求网格中的黑点分布。现有
6*7
的网格 ,在某些格子中有黑点,已知各行与
各列中有黑点的点数之和,
请在这网格中画出黑点的位置。
(这是一网友提出的
题目,说是他笔试时遇到算法题)
#define ROWS 6
#define COLS 7
int iPointsR[ROWS] = {2, 0, 4, 3, 4, 0};
//
各行黑点数
和的情况
. .
. .
.
.
int iPointsC[COLS] = {4, 1, 2, 2, 1, 2, 1};
//
各列黑点数和
的情况
int iCount, iFound;
int iSumR[ROWS], iSumC[COLS], Grid[ROWS][COLS];
int Set(int iRowNo) {
if(iRowNo == ROWS) {
for(int iColNo=0; iColNo < COLS &&
iSumC[iColNo]==iPointsC[iColNo]; iColNo++)
if(iColNo == COLS-1) {
printf(
for(int i=0; i < ROWS; i++)
for(int j=0; j < COLS; j++)
printf(
Grid[j],
(j+1)
%
COLS
?
' ' : 'n');
iFound = 1; // iFound = 1
,有解
}
} else {
for(int iColNo=0; iColNo < COLS; iColNo++) {
if(iPointsR[iRowNo] == 0) {
Set(iRowNo + 1);
} else if(Grid[iRowNo][iColNo]==0) {
Grid[iRowNo][iColNo] = 1;
. .
. .
.
.
iSumR[iRowNo]++;
iSumC[iColNo]++;
if
(iSumR[iRowNo]<=
break-word;
Set(iRowNo);
else if(iSumR[iRowNo]==iPointsR[iRowNo] && iRowNo < ROWS)
Set(iRowNo + 1);
Grid[iRowNo][iColNo] = 0;
iSumR[iRowNo]--;
iSumC[iColNo]--;
}
}
}
return iFound;
//
用于判断是否有解
}
int main(int argc, char* argv[]) {
if(!Set(0))
printf(
}
9
、有
4
种面值的邮票很多枚,这4
种邮票面值分别
1, 4, 12, 21
,现从多中最
多任取
5
进行组合,求取出这些邮票的最续组合值。(据说是华为
2003
年校园
招聘笔试题)
. .
. .
.
.
#define N 5
#define M 5
int k, Found, Flag[N];
int Stamp[M] = {0, 1, 4, 12, 21};
//
在剩余数
n
中组合出面值和
Value
int Combine(int n, int Value) {
if(n >= 0 && Value == 0) {
Found = 1;
int Sum = 0;
for(int i=0; i<=
Sum += Stamp[Flag];
printf(
}
printf(
}else for(int i=1; i0; i++)
if(Value-Stamp >= 0) {
Flag[k++] = i;
Combine(n-1, Value-Stamp);
Flag[--k] = 0;
}
return Found;
}
. .
. .
.
.
int main(int argc, char* argv[]) {
for(int i=1; Combine(N, i); i++, Found=0);
}
10
、大整数数相乘的问题。(这是< br>2002
年在一考研班上遇到的算法题)
void Multiple(char A[], char B[], char C[]) {
int TMP, In=0, LenA=-1, LenB=-1;
while(A[++LenA] != '0');
while(B[++LenB] != '0');
int Index, Start = LenA + LenB - 1;
for(int i=LenB-1; i>=0; i--) {
Index = Start--;
if(B != '0') {
for(int In=0, j=LenA-1; j>=0; j--) {
TMP = (C[Index]-'0') + (A[j]-'0') * (B - '0')
+ In;
C[Index--] = TMP % 10 + '0';
In = TMP / 10;
}
C[Index] = In + '0';
}
}
}
. .
. .
迎战中考-怎样给电脑设密码
迎战中考-怎样给电脑设密码
迎战中考-怎样给电脑设密码
迎战中考-怎样给电脑设密码
迎战中考-怎样给电脑设密码
迎战中考-怎样给电脑设密码
迎战中考-怎样给电脑设密码
迎战中考-怎样给电脑设密码
本文更新与2021-01-21 03:41,由作者提供,不代表本网站立场,转载请注明出处:https://www.bjmy2z.cn/gaokao/542098.html
-
上一篇:事业单位事业单位面试题目经典试题
下一篇:销售面试经典问题