Algorithm on n-bit matrix -

-

दो फ़ंक्शन P1, P2 दिए गए हैं जो इनपुट n-bit x , और y1 = A1 * x, y2 = A2 * x की गणना करें। ए 1 और ए 2 है n * n बिट मैट्रिक्स ये दो फ़ंक्शन n-bit सरणी y1, y2 देता है। हम इन मैट्रिक्स के बारे में कोई जानकारी नहीं जानते हैं लेकिन ए 1 और A2 एक स्लॉट (i, j) को छोड़कर ही पता है । ( i और j हमारे लिए अज्ञात हैं)। हम x के विभिन्न मान के लिए P1 और P2 को कॉल कर सकते हैं और फिर इन दो फ़ंक्शन के आउटपुट की तुलना कर सकते हैं। मुझे यह पता लगाना है कि हम कितने कॉलों के साथ i, j पा सकते हैं?

संक्षिप्त उत्तर में हमारी पुस्तक ने लिखा: लॉग n कॉल कोई संकेत या विचार? सभी के लिए धन्यवाद।

संपादित करें: कोई कहता है, पहले x पर "1 के" का एक स्तंभ मैट्रिक्स होना चाहिए। और y1 और y2 की गणना करें और उस पंक्ति को खोजें जो अलग है फिर x एक मैट्रिक्स बनें जो n / 2 ऊपर तत्व "1" और n / 2 तल तत्व "0 के" हो। अगर y1 और y2 बराबर अंतर n / 2 + 1 से n और हो 1 हो से n / 2 ...

आप कर सकते हैं यदि आप A1 और A2 :

को स्थानांतरित कर सकते हैं, तो आप दो कॉल में यह कर सकते हैं: जांचें कि y1 और y2 में प्रवेश अलग है। यह आपको i देता है।

ट्रांस्पेश <कोड> ए 1 और ए 2 , ऐसा ही करें, जो प्रविष्टि अलग है वह इंडेक्स है j का

स्थानांतरण के बिना: आप अभी भी i को निर्धारित करने के लिए एक गुणा करते हैं। अब, सिर्फ एक "द्विआधारी खोज" करें जहां आपके खोज क्षेत्र को 1 से आपके x वेक्टर के प्रवेश में पहचाना जाएगा।

पहला कदम: x वाले के साथ 1 के आधे को भरें, दूसरे वाला 0 , गुणा करें, जांचें कि क्या सूचकांक i पर प्रविष्टि अलग है, यदि यह नहीं है, तो आपका j दूसरी छमाही में है, यदि यह अलग है, तो यह आपके पहले छमाही में है (जिसे आप 1 के साथ महसूस किया था)

दूसरा चरण: दो चरणों में से पिछले चरण के चयनित हिस्सों में से एक को विभाजित करें, इसका एक आधा 1 से करें और दूसरा 0 के साथ, एक ही तर्क को दोहराने तक, जब तक आप एक ही प्रविष्टि के साथ नहीं छोड़ते वह एक आपके j

का सूचकांक है, चूंकि आप हमेशा 2 में विभाजित हैं, आपके पास बिल्कुल लॉग (n) कॉल होगा। 

  एक कॉल करने से `i` प्रविष्टि निर्धारित करें (तुच्छ) लंबाई = n / 2 start = 0 जबकि (नहीं मिला) var x [start..start + लंबाई] = 1 (0 सभी ओटर प्रविष्टियां) यदि परिणाम 1 [i] == परिणाम 2 [i] प्रारंभ = 0 लंबाई = लंबाई / 2 और शुरू = लंबाई + 1 लंबाई = लंबाई / 2 यदि लंबाई == 1 पाया। आपका सूचकांक जम्मू है

Comments

Post a Comment

Popular posts from this blog

python - Strange behavior using PyQt4's 'pyqtSlot' decorator before another decorator -

-
I have a strange problem with using the QtCore.pyqtSlot decorator in front of the function decorated with a different decorator. The problem below shows this problem, it immediately provides a low QT program with a single button. When pressing a button, the following happens: (1) The signal 'signal_A' and 'signal_B' sequence are connected to method_A and method_B ​​respectively. (2) signal_A and signal_B signals are emitted. (3) The required behavior is that the method_A and method_B ​​are executed. However, it turns out that both signal_A and signal_B trigger method_A, or method_B ​​(oddly, this is nondeterministic, and different for each part of the program!). It appears to be a bug. This issue is present when PyQt4 binding is used in Qt. It is not present when using PySide (use the '-pyside' parameter to verify) I have seen both problems in Python 2 and 3, and both in Windows and Linux This issue is related to the insertion of a decorator be...
Read more

c# - UnhandledExceptionMode.ThrowException for AppDomain.UnhandledException -

-
I want to set unhandledExceptionMode.ThrowException for current AppDomain and not only for application threads. An exception from the second thread should also be handled by my current Donan_Unimated exception handler. Is it possible? Here's my code: Fixed class program {/// & lt; Summary & gt; Main entry point for the application /// & lt; / Summary & gt; [STAThread] static zero major () {applications Set unhandled exception mode (unwanted exception. Throws up); AppDomain.CurrentDomain.UnhandledException + = New UnrestrictedExceptionEndception (CurrentDomain_UnhandledException); Application.EnableVisualStyles (); Application.SetCompatibleTextRenderingDefault (wrong); Application.Run (New Form 1 ()); } Static Zero CurrentDomain_UnhandledException (Object Sender, UnhandledExceptionEventArgs E) {File.AppendAllText ("Log.txt", (Exception) e.ExceptionObject). Message + environment. Newline); }} Maybe you search for the behavior provided by Applic...
Read more

c# - Process.Kill() returns access denied -

-
I'm trying to kill a process using a CMD command line from my C # application, but when I start the application does not happen anything. .. When I try to kill with a command prompt, I get the message: "Access denied" I tried to run as my app administrator and the process was killed. How can I not always use "Run as administrator"? Code: System.Diagnostics.Process process = new System.Diagnostics.Process (); System.Diagnostics.ProcessStartInfo startInfo = New system. Diagnostics. Process STARTINFO (); StartInfo.WindowStyle = System.Diagnostics.ProcessWindowStyle.Hidden; StartInfo.FileName = "cmd.exe"; StartInfo.Arguments = "/ C Tasky / F / IM APP.exe"; Process.start.info = startInfo; Process.start (); try it System.Diagnostics.Process Process = new system Diagnostics Process (); System.Diagnostics.ProcessStartInfo startInfo = New system. Diagnostics. Process STARTINFO (); StartInfo.WindowStyle = System.Diagnostics.ProcessWindowS...
Read more