【模拟】蓝桥杯试题 幸运数_蓝桥杯幸运数字哈沙德数c++

题目描述

OJ地址 http://lx.lanqiao.cn/problem.page?gpid=T33

幸运数是波兰数学家乌拉姆命名的。它采用与生成素数类似的“筛法”生成。

首先从1开始写出自然数1,2,3,4,5,6,…

1 就是第一个幸运数。

我们从2这个数开始。把所有序号能被2整除的项删除，变为：

1 _ 3 _ 5 _ 7 _ 9 …

把它们缩紧，重新记序，为：

1 3 5 7 9 … 。这时，3为第2个幸运数，然后把所有能被3整除的序号位置的数删去。注意，是序号位置，不是那个数本身能否被3整除!! 删除的应该是5，11, 17, …
此时7为第3个幸运数，然后再删去序号位置能被7整除的(19,39,…)

最后剩下的序列类似：

1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, 43, 49, 51, 63, 67, 69, 73, 75, 79, …

输入：

输入两个正整数m n, 用空格分开 (m < n < 1000*1000)

输出：

程序输出 位于m和n之间的幸运数的个数（不包含m和n）。

样例输入1：

1 20
1

样例输出1：

5
1

样例输入2：

30 69
1

样例输出2：

8
1

思路：

弄一个链表，把1到m之间的数，每个数做一个节点，然后再考虑删除的操作，链表的删除，删除最后一个节点的时候要考虑周到一些，为了方便，链表我用的双向链表。

​ 记录当前的幸运数luck和当前幸运数在第index个节点上。依次遍历每个链表中的每个节点，如果遍历第 i 个节点时，i（节点的序号）是luck的整数倍，那就删除这个节点。

​ 删除完毕后，新的幸运数也就出现了，index后移一位就是新的幸运数所在的节点序号，遍历到第index++个节点，就可以取到新的幸运数luck。然后判断luck是否满足 大于 n 小于 m，满足的话就计数，否则再判断一下幸运数是不是链表的最后一个节点了，如果是的话，就结束所有的循环吧。因为整个链表长度为m，最后一个数是m，幸运数也不可能大于等于m，所以一定在m以内，一翻操作之后，不是幸运数的都删没了，所以一个幸运数的后边如果是NULL（没有节点了），那就不用再进行删除操作了，所有的幸运数都已经找到（链表中的节点都是幸运数）。

代码

#include <bits/stdc++.h>

using namespace std;

int ans[1005];

struct node{
	int data;
	node* next;
	node* pre;
};

node* creatlist(int n){   // 双向链表 
	node *head,*tail,*cur;
	head = (node *)malloc(sizeof(node));
	tail = head;
	
	for(int i = 0; i < n-1; i++){   // 除去head  还有n-1个节点 
		cur = (node *)malloc(sizeof(node));
		tail -> next = cur;
		cur -> pre = tail;
		tail = cur;	
	}
	
	tail -> next = NULL;

	return head;
} 

int main(){
	
	int n,m,ans = 0;
	cin >> n >> m;
	node *list = creatlist(m);  //最长就m个节点够了 幸运数 < m 
	node *tmp = list;

	for(int i = 1; i <= m; i++){
		tmp -> data = i;
		tmp = tmp -> next;
	}

	node *cur = list -> next;   //从第二个节点开始 
	int luck = 2;  //当前的幸运数 （要删除的下标）   2其实并不是幸运数，但是这里以2开始删除 
	int index = 1;  //幸运数在第几个节点上 
	
	while(1){
		// 从第二个节点开始操作  因为第一个节点是1 
		for(int i = 2; cur != NULL ; i++){   // 第i个节点 

			if(i % luck == 0){
				// 删除该节点 
				if(cur -> next == NULL){
					// 删除为节点要注意 
					cur -> pre -> next = NULL;   //倒数第二个节点为尾节点 
					free(cur);
					cur = NULL;
				}
				else{
					cur -> pre -> next = cur -> next;
					cur -> next -> pre = cur -> pre;
					node *t = cur -> next;
					free(cur); 
					cur = t;
				} 
				
			}else{
				cur = cur -> next;
				// 检查下一个节点 
			}

		}
		//删除完毕 幸运数下标后移一位，得到新的幸运数的位置（当前幸运数在第几个节点上） 
		index++;
		tmp = list;   // 从链表头开始
		for(int i = 0 ; i < index;i++){  //获取当前的幸运数 
			if(tmp != NULL){
				luck = tmp -> data;
				tmp = tmp -> next; 
			} 
		}

		cur = list -> next;  // 恢复指针  准备下一次的while循环 从第2个节点开始 
		
		if(luck > m){
			break;
		}else if(luck > n && luck < m){   // 在n和m之间  不包括 n和m  计数 
			ans++;
		}
		
		if(tmp == NULL){   // 幸运数是 最后一个节点 代表所有的节点都考虑过了 跳出while 
			break;
		}
		
	}

	cout << ans << endl;

	return 0;	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99