Hitung akar kuadrat hanya menggunakan ++

13

Tugas Anda adalah menghitung akar kuadrat dari bilangan bulat positif tanpa menggunakan operator matematika untuk mengubah angka, seperti:

  • Mengatur variabel (mis. SquareRoot = 5)
  • Penambahan (A + B)
  • Pengurangan (AB)
  • Perkalian (A * B)
  • Divisi (A / B)
  • Akar kuadrat, kubus, keempat, dll
  • Eksponen

Operator perbandingan (seperti <,>, ==, dll) tidak dianggap sebagai "operator matematika" untuk keperluan pertanyaan ini dan diizinkan selama mereka tidak mengubah nilai suatu variabel.

Satu-satunya operator yang dapat Anda gunakan adalah ++. Pengecualian berikut berlaku:

  • Jika mau, Anda dapat menginisialisasi variabel dengan mengaturnya ke 0.
  • Jika bahasa Anda tidak termasuk sintaks ++, Anda dapat menggunakan sintaks yang setara, seperti foo + = 1 atau foo = foo + 1
  • Akar kuadrat harus dihitung setidaknya 6 digit di luar desimal (tempat seratus-ribu) dan dikeluarkan sebagai jumlah total desimal (mis. Jika saya input 2 itu bisa keluar sebagai 14142135624 atau 1414213 tergantung pada pembulatan) . Membulatkan ke atas atau ke bawah tidak penting.

Fungsi yang ditentukan pengguna tidak diizinkan. Selain itu, fungsi simulasi dengan goto juga tidak diperbolehkan.

Saya tertarik melihat apa yang diajukan semua orang! Selamat coding!

KLARIFIKASI

Jelaskan bahwa angka adalah bilangan bulat positif. Anda boleh membuat kode yang dapat melakukan nomor apa pun tetapi tidak perlu.

KLARIFIKASI # 2

Jelaskan bahwa operator perbandingan diizinkan.

KLARIFIKASI # 3

Penambahan, pengurangan, penggandaan, pembagian, dan fungsi untuk mengubah angka tidak diperbolehkan sama sekali , terlepas dari apakah mereka disimpan ke variabel atau tidak. Saya minta maaf karena ini membatalkan pasangan jawaban yang ada, tetapi saya bermaksud mendefinisikan grup operator ini dengan "ubah nomor" untuk mencegah jawaban troll (mis. Saya hanya menggunakan fungsi sqrt (), Anda hanya melarang penambahan, perkalian, pembagian, dan pengurangan). Maaf bila membingungkan.

KLARIFIKASI # 4

Jelaskan bahwa kita membutuhkan setidaknya 5 digit. 10 digit menyebabkan kode berjalan untuk waktu yang lama.

iggyvolz
sumber
1
Tidak, - tidak diizinkan, maaf atas kebingungan! Saya awalnya berencana untuk memiliki ++ dan - tetapi saya memutuskan untuk mengeluarkannya pada menit terakhir.
iggyvolz
5
"tanpa menggunakan operator matematika untuk mengubah angka" - Saya pikir ini mungkin perlu klarifikasi. Maksud Anda bahwa operator ini mungkin tidak digunakan sama sekali , atau bahwa mereka dapat digunakan, tetapi hanya jika hasilnya tidak disimpan ke variabel, misalnya while r*r<n*10e20:r+=1- cukup sepele. Juga, Anda dapat mempertimbangkan mengurangi output yang diperlukan menjadi 10 ^ 8 atau lebih. Pertama, karena 10 ^ 10 lebih besar dari 2 ^ 31, dan kedua, karena akan butuh beberapa saat untuk meningkatkan setinggi itu.
primo
1
Mengapa Anda pernah ingin "perubahan" variabel sama sekali? Kalian yang imperatif punya cara berpikir yang aneh ...
berhenti mengubah counterclock dengan
4
Saya menandai untuk menutup pertanyaan ini. Banyak perubahan radikal pada pertanyaan. Anda seharusnya benar-benar mendapatkan pertanyaan ini divalidasi melalui Sandbox atau Anda akan membuat frustasi orang-orang yang berinvestasi dalam upaya menjawab.
Abhijit
3
Mengurangi jumlah digit yang diperlukan tidak ada artinya tanpa batas waktu / memori. Kode saya dapat menangani 5 digit, tetapi mesin saya tidak memiliki cukup RAM.
Dennis

Jawaban:

13

Python 66

print'%.0f'%reduce(lambda a,b:abs(a)+1e10j,range(-2,input())).real

Keluaran

>>> print'%.0f'%reduce(lambda a,b:abs(a)+1e10j,range(-2,input())).real
121
110000000000
>>> print'%.0f'%reduce(lambda a,b:abs(a)+1e10j,range(-2,input())).real
1000
316227766017

Solusi ini menggunakan Spiral of Theodorus pada bidang yang kompleks untuk mencapai hasil.

Abhijit
sumber
2
Saya pikir itu perlu dibungkus int(...*1e10), jika tidak sangat bagus. Meskipun, mengambil absnilai yang kompleks kurang lebih sqrtmenyamar.
Primo
1
@primo Saya rasa Anda tidak diizinkan *1e10...
Cruncher
@ primo: Alih-alih mengalikan dengan 1e10, saya mengambil rute yang sedikit berbeda. Dan meskipun saya setuju bahwa abs mungkin sqrt dalam penyamaran, namun saya merasa sepenuhnya legal seperti yang dinyatakan dalam masalah ini.
Abhijit
Saya melihat downvote, dan itu sangat menyedihkan. Saya memiliki harapan besar untuk jawaban ini, jadi siapa pun yang downvoting, silakan tinggalkan komentar.
Abhijit
9
@iggyvolz: Saya benar-benar terkejut bahwa Anda terus memperluas pertanyaan Anda dan menambahkan lebih banyak batasan. Orang menginvestasikan waktu dan upaya untuk menulis jawaban dan Anda tidak dapat mengharapkan mereka menjadi psikis.
Abhijit
6

Python, 184 karakter

Solusi Python berikut hanya menggunakan operator increment dan tidak ada operator aritmatika sama sekali. Namun, dengan presisi yang diperlukan (10 digit), dibutuhkan waktu yang sangat lama untuk dijalankan. Anda dapat mengujinya dengan presisi lebih rendah (3 digit) dengan mengurangi 1e20menjadi 1e6.

import sys;t=0
for _ in range(int(sys.argv[1])):
 for _ in range(int(1e20)):t+=1
q=0
while 1:
 z=0
 for _ in range(q):
  for _ in range(q):z+=1
 if z>=t:break
 q+=1
print(q)

Tidak Disatukan:

import sys

# t = N * 100000000000000000000 (magnitude of twice the precision)
t = 0
for _ in range(int(sys.argv[1])):
    for _ in range(int(1e20)):
        t += 1
q = 0
while True:
    # z = q * q
    z = 0
    for _ in range(q):
        for _ in range(q):
            z += 1
    if z >= t:
        break
    q += 1
print(q)
Greg Hewgill
sumber
Saya mengklarifikasi pertanyaan, Anda dapat melakukannya hingga sebanyak digit yang Anda inginkan (setidaknya 5). Saya tidak terbiasa dengan python, tapi saya berasumsi bahwa int () hanya tipe caster? Jika demikian, itu baik-baik saja karena tidak mengubah nilai angka.
iggyvolz
@iggyvolz: Benar, Anda perlu itu untuk mengkonversi nilai argumen string (ditentukan pada baris perintah) ke integer. Fungsi sederhana tidak membutuhkan itu.
Greg Hewgill
2

Fortran 73

read*,t;s=0;do while(abs(s*s/1e10-t)>1e-10);s=s+1;enddo;print*,s/1e5;end

Mungkin butuh sedikit waktu untuk benar-benar menentukan jawaban untuk nilai-nilai tertentu, tetapi pasti akan berhasil. Sementara saya menggunakan *dan -, ini tidak mengubah nilai apa pun , hanya yang s=s+1benar - benar mengubah apa pun.

Kyle Kanos
sumber
Wow, saya kira saya tidak berpikir untuk menggunakan operator untuk mengubah nilai statis. Tidak apa-apa dan +1 (jika saya memiliki 15 reputasi yang perlu
ditingkatkan
Ini menggunakan *operator, yang jelas tidak diizinkan. Atau apakah saya entah bagaimana salah memahami pembatasan yang diberikan?
Greg Hewgill
@GregHewgill: Status OP, tanpa menggunakan operator matematika untuk mengubah nomor ; operator ini tidak mengubah nilai apa pun.
Kyle Kanos
7
Tapi itu masih menggunakan *operator untuk mengubah nomor, Anda hanya tidak menyimpan hasilnya di mana pun. Jika OP hanya ingin melarang penugasan (selain dari s=s+1), lalu mengapa menyebutkan semua operator aritmatika yang tidak diizinkan?
Greg Hewgill
1
@iggyvolz: Mengubah aturan ~ 20 jam kemudian adalah bentuk yang buruk. Tolong jangan lakukan itu dan gunakan kotak pasir untuk mengetahui kekusutan dalam masalah Anda sebagai gantinya.
Kyle Kanos
2

CJam, 26 byte

q~,1e20,m*,:N!{)_,_m*,N<}g

Cobalah online.Tempel Kode , ketik bilangan bulat yang diinginkan di Input dan klik Run . Sebelum Anda melakukannya, saya sarankan 1e10untuk mengubahnya 1e4.

The interpreter Java menangani 1e6dengan masukan “2” dalam waktu sekitar 15 detik. 1e20akan membutuhkan sejumlah besar RAM.

Contohnya

$ cjam <(echo 'q~,1e2,m*,:N!{)_,_m*,N<}g') <<< 4; echo
20
$ cjam <(echo 'q~,1e2,m*,:N!{)_,_m*,N<}g') <<< 2; echo
15
$ cjam <(echo 'q~,1e4,m*,:N!{)_,_m*,N<}g') <<< 4; echo
200
$ cjam <(echo 'q~,1e4,m*,:N!{)_,_m*,N<}g') <<< 2; echo
142
$ cjam <(echo 'q~,1e6,m*,:N!{)_,_m*,N<}g') <<< 4; echo
2000
$ cjam <(echo 'q~,1e6,m*,:N!{)_,_m*,N<}g') <<< 2; echo
1415

Latar Belakang

Karena kami tidak diizinkan operator matematika untuk mengubah angka, kami akan menggunakan operator setwise untuk mengubah array.

Kode dimulai dengan "mengalikan" input ("i") dengan 1e20, tetapi tanpa perkalian yang sebenarnya. Sebagai gantinya, kami mendorong sebuah array yang berisi bilangan bulat "i", sebuah array yang mengandung bilangan bulat 1e20, mengambil produk cartesian mereka dan menghitung panjangnya.

Kemudian, kami mendorong nol dan kenaikan sampai produk bilangan bulat dengan sendirinya (dihitung seperti di atas) tidak lagi lebih kecil dari i * 1e20. Ini menyebabkan akar kuadrat untuk dibulatkan.

Bagaimana itu bekerja

q~     " Read for STDIN and interpret. ";
,      " Push an array containing that many integers. ";
1e20,  " Push the array [ 0   …   1e20 - 1]. ";
m*,:N  " Get the length of the cartesian product and save it in “N”. ";
!      " Logical NOT. Since the input is a positive integer, this pushes 0. " ;
{      " ";
  )    " Increment the integer on the stack.";
  _,   " Push an array containing that many integers. ";
  _m*, " Get the length of the cartesian product of the array by itself. ";
  N<   " If the product is smaller than the target value, push 1; otherwise push 0. ";
}g     " Repeat the loop if the result was 1. ";
Dennis
sumber
1

Cobra - 62

Diposting sebelum edit ketiga, tidak lagi valid.

Tidak hanya pendek, tetapi harus bebas dari luapan n < Decimal.maxValue

def f(n)
    r,e=0d,10000000000
    while r/e*r/e<n,r+=1
    print r
Suram
sumber
Tapi Anda menggunakan r/e*r/e, yang jelas merupakan ++operator non- matematika ...
nneonneo
@nneonneo ini diposting sebelum edit ketiga, dan saya belum mengubahnya
Οurous
0

Scala, 117

val z=BigInt(readLine+"0000000000")
print(Stream.from(1)find(x=>(BigInt(0)/:Stream.fill(x,x)(1).flatten){_+_}>=z)get)

Tidak menyelesaikan dalam jumlah waktu yang wajar, bahkan untuk 2 sebagai input, tetapi berhasil. Anda mungkin memperhatikan bahwa saya melakukannya _+_, tetapi itu hanya menambah 1, dan Scala tidak memiliki ++operator. Saya dapat menyimpan dua karakter dengan mengganti Stream bagian dalam dengan List, tetapi kemudian memori akan habis. Seperti yang tertulis, saya pikir ini hanya berskala dalam waktu pemrosesan, bukan penggunaan memori.

Joe K.
sumber
0

Haskell, 70 byte

s i|r<-[1..i]=foldl1(.)[(+1)|j<-r,k<-r]
f i=[j-1|j<-[0..],s j 0>=i]!!1

fmemberikan akar kuadrat integer dengan menemukan angka terbesar yang kuadratnya kurang dari atau sama dengan input. Fungsi kuadrat s ibertambah satu untuk setiap elemen (i,i)matriks. (Diketik di ponsel, jadi mungkin ada kesalahan ketik).

Michael Klein
sumber
0

PHP, 124 byte

Ini adalah algoritma yang lengkap. Itu hanya mencoba angka sampai kuadrat dari angka itu lebih besar dari angka "goal" (yang merupakan kali input 1E number of decimalskuadrat (10.000 untuk hasil 2 desimal). Kemudian ia mencetak angka terakhir.

for(;$a++<$z=$argv[1];)for(;$$a++<1e6;)$g++;for(;$b++<$g;$i=$x=0)for(;$i++<$b;)for($j=0;$j++<$b;)if(++$x>=$g)break 3;echo$b;

Jalankan seperti ini ( -dditambahkan hanya untuk alasan estetika):

php -d error_reporting=32757 -r 'for(;$a++<$z=$argv[1];)for(;$$a++<1e6;)$g++;for(;$b++<$g;$i=$x=0)for(;$i++<$b;)for($j=0;$j++<$b;)if(++$x>=$g)break 3;echo"$b\n";' 2

Jangan rekomendasikan untuk mencoba ini dengan lebih dari 3 desimal atau angka di atas 10.

aross
sumber