javascript - pengaturcaraan, masalah algoritma

Question

Saya mempunyai soalan temu duga sehari sebelum semalam
Sila gunakan bahasa seperti js, python, java, c, c++ untuk mengira 10 bilion data dalam 10 saat, dan selesaikannya (hanya dalam masa 3 saat), nombor genap datang sebelum ini nombor ganjil
Formatnya adalah seperti berikut
1, 2, 3, 4, 5
Hasil output ialah
2, 1, 4, 3, 6, 5,
Soalan 2: Pada kod 1, adalah dikehendaki bahawa kata kunci sementara tidak boleh digunakan, bermula dari 100 Dapatkan semua nombor perdana daripada 100 juta (masa tidak boleh melebihi 3 saat)
Bagaimana untuk melakukan ini?

Answer 1

Saya tidak faham soalan pertama Adakah ini bermakna dua nombor adalah pasangan, dan nombor genap didahului oleh nombor ganjil?

Soalan kedua adalah mudah Jika anda tidak boleh menggunakan gelung, gunakan lelaran tatasusunan.

Answer 2

Sebut yang mana php 的 foreach tidak penting (ketawa

Saya rasa niat penemuduga adalah untuk meminta anda menulis fungsi rekursif? Saya rasa begitu.

Answer 3

Saya ada soalan temuduga sehari sebelum semalam
Sila gunakan bahasa seperti js, python, java, c, c++ untuk mengira 10 bilion data dalam 10 saat, dan selesaikannya (hanya dalam masa 3 saat), nombor genap datang sebelum nombor ganjil
Formatnya adalah seperti berikut
1, 2, 3, 4, 5
Hasil output ialah
2, 1, 4, 3, 6, 5,
Soalan 2: Di atas kod dalam 1, ia diperlukan bahawa kata kunci sementara tidak boleh digunakan, daripada Dapatkan semua nombor perdana daripada 10 bilion (masa tidak boleh melebihi 3 saat)
Bagaimana untuk melakukan ini?

---

Memandangkan ia tidak boleh digunakan untuk sementara waktu

Maka prestasi rekursif tidak mencukupi. . . Tetapi saya masih menggunakan beberapa. . For Performance

Mungkin ada cara yang bijak

. . . 100亿 Saiz sepatutnya ada. Saya belum jumpa lagi.

Kod

10 billion besar sikit, saya ambil 100,000 dulu

var n = 1000 * 1000; 
var test = new Array(n).fill(n).map((e, idx) => idx); 

Dengan cara ini, anda boleh mendapatkan susunan nombor asli dengan panjang 100,000.

---

Seterusnya

1. Nombor genap dahulu, nombor ganjil diakhiri

Selepas pemerhatian, saya dapati 奇数 + 1、 偶数 - 1 baik

var isEven = n => n % 2 === 0; 

var res001 = test.map((e, idx) => {
    if (isEven(e)){
        return e - 1; 
    } else {
        return e + 1; 
    }
}); 

Lengkapkan soalan pertama

ScreenShot One

Seterusnya

Soalan seterusnya ialah mendapatkan nombor perdana berdasarkan perkara di atas iaitu dapatkan semua nombor perdana daripada zs

Saya mencari isu tentang nombor perdana, dan orang lain berkata 质数分布在 6 的倍数的左边或者右边 Kemudian saya hanya perlu melintasi sisi kiri dan kanan setiap gandaan 6 dan menentukan sama ada ia nombor perdana.

Pautan: Menentukan sama ada nombor ialah nombor perdana/nombor perdana - daripada algoritma penghakiman biasa kepada idea algoritma penghakiman yang cekap

// 剔除第一个负数 
var zs = res001.slice(1); 

var is6x = n => n % 6 === 0; 


var isPrime = n => {
     let temp = Math.sqrt(n);  
     
     for(let i = 2; i <= temp; i++){
         if(n % i === 0){
             return false; 
         }
     }
     
     return true;  
}  


var lasts = zs.filter(is6x).reduce((acc, cur) => {
    let left = cur - 1, right = cur + 1; 
    if (isPrime(left)) acc.push(left); 
    if (isPrime(right)) acc.push(right); 
    
    return acc; 
}, []); 

console.log(lasts); 

ScreenShot Dua

Saya tidak tahu sama ada ia betul...

Tetapi kita masih perlu meletakkan semula nombor perdana 1 2 3 5 daripada 小于 6 secara berasingan. (Tiada ejaan di sini)

Prestasi

Patuhi kod yang tertulis di atas

var isEven = n => n % 2 === 0; 


var is6x = n => n % 6 === 0; 

var isPrime = n => {
     let temp = Math.sqrt(n);  
     
     for(let i = 2; i <= temp; i++)
        if(n %i== 0){
            return false; 
        }
     return true;  
}  


function timeTest(n){
    var test = new Array(n).fill(n).map((e, idx) => idx); 
    var res001 = test.map((e, idx) => {
        if (isEven(e)){
            return e - 1; 
        } else {
            return e + 1; 
        }
    }); 
    var zs = res001.slice(1); 
    
    var lasts = zs.filter(is6x).reduce((acc, cur) => {
        let left = cur - 1, right = cur + 1; 
        if (isPrime(left)) acc.push(left); 
        if (isPrime(right)) acc.push(right); 
        
        return acc; 
    }, []); 
    
    return lasts; 
}

ujian

var n = 1000 * 10000; 

console.time('1000 万')
timeTest(n); 
console.timeEnd('1000 万');

1000 万 Hasilnya seperti dalam gambar

---

Ia mengambil masa 13.8 saat. Tidak mustahil untuk melengkapkan volum 13.8 秒 不可能做到 10 + 3 秒内完成 100亿 dalam 10 + 3 saat.

Komputer saya ialah i5-4210M 12G Chrome 58

JavaScript tidak boleh mencapai prestasi ini: JavaScript 做不到这样的性能： 100亿 个数字 13 nombor dalam 13 saat....

Beberapa G data...

Mengikut idea di atas, walaupun C/C++ dianggarkan sukar untuk berlari 10 bilion dalam masa 13 saat.

Fokus untuk menyelesaikan masalah.

Pautan

Tentukan sama ada nombor ialah nombor perdana/nombor perdana - daripada algoritma penghakiman biasa kepada idea algoritma penghakiman yang cekap

Answer 4

Pertama sekali, terima kasih atas algoritma untuk mencari nombor perdana di tingkat atas saya akan menyiarkan keputusan dan kod saya (hanya 10 juta, 100 juta pelayar meletup secara langsung, dan rekursi tidak boleh digunakan untuk mencari nombor perdana (hasil ujian saya). jika tidak, saya perlu Meletup, hanya boleh lelaran).

Hasil dalam pelayar:

Hasilnya dalam

nod:

var arr = [];

console.time("1000万");
for( var i = 1; i <= 10000000; i++ ){
    arr.push(i);
}

for( var j = 0, len = arr.length;j < len; j+=2 ){
    arr[j]++;
    arr[j+1]--;
}

function isPrime(num,sqrt){
     if(num == 1)
     return false;
     if(num == 2 || num == 3 )  
     return true;  
     if(num % 6 != 1 && num % 6 != 5)  
     return false;  
     var tmp = sqrt(num);  
     for(var i= 5;i<=tmp; i+=6 )  
        if(num % i == 0 || num % ( i + 2) == 0 )  
        return false ;  

     return true;  
};

function getPrime(sourceArray,array,isPrime,sqrt){

    sourceArray.map(function(num,idx){
        if(isPrime(num,sqrt)){
            array.push(num);
        }
    });

    return array;
};

var result = getPrime(arr,[],isPrime,Math.sqrt);

console.timeEnd("1000万");