偶然看到群里別人發的一條面試題
生成亂數 (由0~9的阿拉伯數字組成的，長度是6~15個字符)
要求
1. 不能出現連續3個以上相同的數字(11234,2333456 是不允許的)
2. 不能出現3個連號的情況( 123456, 123457, 2567891)
3. 生成的字串不能是等引數列
4. 要求演算法高效，少占記憶體。
我是沒什么好辦法。大概三步走
第一步
生成亂數
一次生成64位的數，再做隨機長度分割。
第二步
每個字串從頭到尾遍歷，檢查是否有三個連續數字一致，同時也檢查是否有連續3個連號。
若有則該數失敗。
第三步
依次遍歷，判斷等引數列
拋轉引玉，有沒有更高效的辦法來解這個題？！
uj5u.com熱心網友回復：
第二步每個字串從頭到尾遍歷，檢查是否有三個連續數字一致，同時也檢查是否有連續3個連號。
若有則該數失敗。
別失敗呀
簽名那么多步驟 別浪費了
你交換一下不就不會失敗了么
比如
111234
交換一下變成
121314
不就完事了
uj5u.com熱心網友回復：
分段隨機就可以了先隨機6-15 作為位數
然后每次隨機1位數作為組成部分
每次隨機檢查會不會重復前面的數字 會不會和前面的數字連號
就可以了
uj5u.com熱心網友回復：
僅供參考：//要求1:從給出來的不同的六組數字中，從每組任意挑選一個數字，最后組成一個六個數字的陣列。
//將所有的陣列全部列出來。
//同時，排除全部為偶數、全部為奇數的陣列。
//排除四個數字遞增連續（比如8、9、10、11）的陣列。
//如下：
//第一個數字從這12個數字中挑選：,1,3,2,4,5,6,7,8,9,10,11,12
//第二個數字從這17個數字中挑選：,8,7,5,9,6,4,11,10,12,13,3,14,17,2,16,15,18
//第三個數字從這21個數字中挑選：,13,10,15,16,18,11,14,12,7,19,21,17,8,22,9,20,6,23,5,24,25
//第四個數字從這20個數字中挑選：,22,23,18,20,16,17,15,21,14,26,19,24,27,25,12,13,11,10,28,29
//第五個數字從這19個數字中挑選：,26,25,27,29,30,28,23,24,20,22,19,31,21,17,18,32,13,15,16
//第六個數字從這14個數字中挑選：,32,33,30,31,29,28,27,26,25,24,23,22,18,21
//要求2:
//請輸入第1個數字的選擇范圍：（可以手動輸入任意幾個空格間隔的數字,最多30個）
//請輸入第2個數字的選擇范圍：（可以手動輸入任意幾個空格間隔的數字,最多30個）
//請輸入第3個數字的選擇范圍：（可以手動輸入任意幾個空格間隔的數字,最多30個）
//請輸入第4個數字的選擇范圍：（可以手動輸入任意幾個空格間隔的數字,最多30個）
//請輸入第5個數字的選擇范圍：（可以手動輸入任意幾個空格間隔的數字,最多30個）
//請輸入第6個數字的選擇范圍：（可以手動輸入任意幾個空格間隔的數字,最多30個）
//然后回車，輸出結果到cp.txt
//要求3:
//保證同一組資料的數都不相同。
//比如，第一個數為6時，第二個數或其他的數都不能再為6；第二個數為10時，第三個數或其他的數都不能再為10，以此類推……
//要求4:
//增加一個條件：在產生的每個陣列A1A2A3A4A5A6中，要求A1<A2<A3<A4<A5<A6
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int v[6];
int n[6]={12,17,21,20,19,14};
int d[6][30]={
{1,3,2,4,5,6,7,8,9,10,11,12},
{8,7,5,9,6,4,11,10,12,13,3,14,17,2,16,15,18},
{13,10,15,16,18,11,14,12,7,19,21,17,8,22,9,20,6,23,5,24,25},
{22,23,18,20,16,17,15,21,14,26,19,24,27,25,12,13,11,10,28,29},
{26,25,27,29,30,28,23,24,20,22,19,31,21,17,18,32,13,15,16},
{32,33,30,31,29,28,27,26,25,24,23,22,18,21},
};
int i,j,i0,i1,i2,i3,i4,i5,s;
char ln[100],*t;
FILE *f;
int main() {
for (i=0;i<6;i++) {
printf("請輸入第%d個數字的選擇范圍：",i+1);
fgets(ln,100,stdin);
j=0;
t=strtok(ln," ");
while (1) {
if (NULL==t) break;
if (0==t[0]) continue;//跳過多個空格間隔時取出的空串
d[i][j]=atoi(t);
j++;
if (j>=30) break;
t=strtok(NULL," ");
}
n[i]=j;
}
f=fopen("cp.txt","w");
if (NULL==f) {
printf("無法生成cp.txt!\n");
return 1;
}
printf("正在生成cp.txt...");
for (i0=0;i0<n[0];i0++) {
for (i1=0;i1<n[1];i1++) {
for (i2=0;i2<n[2];i2++) {
for (i3=0;i3<n[3];i3++) {
for (i4=0;i4<n[4];i4++) {
for (i5=0;i5<n[5];i5++) {
v[0]=d[0][i0];
v[1]=d[1][i1];
v[2]=d[2][i2];
v[3]=d[3][i3];
v[4]=d[4][i4];
v[5]=d[5][i5];
if (0==(v[0]%2)
&& 0==(v[1]%2)
&& 0==(v[2]%2)
&& 0==(v[3]%2)
&& 0==(v[4]%2)
&& 0==(v[5]%2)) continue;//排除全部為偶數
if (1==(v[0]%2)
&& 1==(v[1]%2)
&& 1==(v[2]%2)
&& 1==(v[3]%2)
&& 1==(v[4]%2)
&& 1==(v[5]%2)) continue;//排除全部為奇數
for (i=0;i<5;i++) {
for (j=i+1;j<6;j++) {
if (v[i]==v[j]) goto NEXT;//保證同一組資料的數都不相同
}
}
NEXT:
if (i>=5) {
for (i=0;i<5;i++) for (j=i+1;j<6;j++) if (v[i]>v[j]) {s=v[i];v[i]=v[j];v[j]=s;}//從小到大排序
if ((v[0]+1==v[1]
&& v[1]+1==v[2]
&& v[2]+1==v[3])
|| (v[1]+1==v[2]
&& v[2]+1==v[3]
&& v[3]+1==v[4])
|| (v[2]+1==v[3]
&& v[3]+1==v[4]
&& v[4]+1==v[5])) continue;//排除四個數字遞增連續
fprintf(f,"%2d,%2d,%2d,%2d,%2d,%2d\n",v[0],v[1],v[2],v[3],v[4],v[5]);
}
}}}}}}
fclose(f);
printf("\n生成cp.txt完畢\n");
return 0;
}
//如果檔案in.txt的內容為
//1 3 2 4 5 6 7 8 9 10 11 12
//8 7 5 9 6 4 11 10 12 13 3 14 17 2 16 15 18
//13 10 15 16 18 11 14 12 7 19 21 17 8 22 9 20 6 23 5 24 25
//22 23 18 20 16 17 15 21 14 26 19 24 27 25 12 13 11 10 28 29
//26 25 27 29 30 28 23 24 20 22 19 31 21 17 18 32 13 15 16
//32 33 30 31 29 28 27 26 25 24 23 22 18 21
//可以在cmd視窗里面輸入命令
//cp <in.txt
//得到要求1對應的結果
//BTW:中了一定要分我六成啊！嘿嘿！(^=^)
uj5u.com熱心網友回復：
等引數列只是一種例舉的規律...是不是還有其他的規律？uj5u.com熱心網友回復：
還要保證生成50萬個不同的亂數uj5u.com熱心網友回復：
問題簡化，就只考慮等差吧。
uj5u.com熱心網友回復：
確實 50萬個，得用hash 或者 樹 或者 跳表 的資料結構來保存 已有的亂數， 每次生成了一堆亂數，還得先做查重。
uj5u.com熱心網友回復：
趙老師一如既往地犀利， 數十年如一日， 想當初10年前我剛進CSDN的時候，趙老師就猶如指路明燈，照耀著我一路從菜鳥變成了老鳥。
uj5u.com熱心網友回復：
隨機必然有重復，所謂“不重復的隨機”實際上是洗牌。洗牌演算法參考下面：#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int d[6];
int i,n,a,b,t;
int c,j;
void main() {
srand(time(NULL));
printf("shuffle 0..n-1 demo\n");
for (n=1;n<=5;n++) {/* 測驗1～5個元素 */
printf("_____n=%d_____\n",n);
j=1;
for (c=1;c<=n;c++) j=j*c;/* j為n! */
j*=n*2;
for (c=1;c<=j;c++) {/* 測驗n*2*n!次 */
for (i=0;i<n;i++) d[i]=i;/* 填寫0～n-1 */
for (i=n;i>0;i--) {/* 打亂0～n-1 */
a=i-1;b=rand()%i;
if (a!=b) {t=d[a];d[a]=d[b];d[b]=t;}
}
printf("%04d:",c);
for (i=0;i<n;i++) printf("%d",d[i]);
printf("\n");
}
}
printf("shuffle 1..n demo\n");
for (n=1;n<=5;n++) {/* 測驗1～5個元素 */
printf("_____n=%d_____\n",n);
j=1;
for (c=1;c<=n;c++) j=j*c;/* j為n! */
j*=n*2;
for (c=1;c<=j;c++) {/* 測驗n*2*n!次 */
for (i=1;i<=n;i++) d[i]=i;/* 填寫1～n */
for (i=n;i>1;i--) {/* 打亂1～n */
a=i;b=rand()%i+1;
if (a!=b) {t=d[a];d[a]=d[b];d[b]=t;}
}
printf("%04d:",c);
for (i=1;i<=n;i++) printf("%d",d[i]);
printf("\n");
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/284983.html
標籤：其它技術問題