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

c# - XML serialize base class without knowing derived class -

-
I know that a XmlSerializer throws an exception if the type passed does not match the type Since then the serializer was created My question is: Is it possible to serial the base type without knowing the derivative type? Consider the following scenario: The following classes are in a top-level domain and there is no dependency : Public Class Serializer {Private Static String Serialize (base basedata) {var serializer = New XML serializer (typefile); Var sb = new stringbilder (); (Var author = XmlWriter.Create (sb)) using {serializer.Serialize (author, bassadata); } Return sb.ToString (); } Private static string Deserialize (...) {...}} Public class base {public string name {get; Set; }} The following derivative classes have additional dependencies on things like UI components, structure, etc. (and more on this later): [Export (Typ (IMyComponent)] Public category was created: Base, IMyComponent, INotifyPropertyChanged {public new string name {get {return base.Name; ...
Read more

sql - Find last match with latest inserted name in table -

-
मेरे पास एक टेबल है PersonalInfo जैसे कॉलम जैसे आईडी, नाम, पता । मान लें कि मेरा डेटा निम्न है 1 जॉन यूएस 2 मार्क यूके 3 जॉन यूके 4 डेविड यूएस अब जब मैं नया रिकार्ड निम्न सम्मिलित करता हूं 5 जॉन चीन मैं पिछले रिकार्ड को उसी नाम के रूप में अद्यतन करना चाहता हूँ जैसा कि उदाहरण के लिए नया है जैसा कि यहां दिखाया गया है 3 जॉन यूके को 3 जॉन चीन पर अपडेट कर दिया जाएगा। जब मैं 5 वीं रिकॉर्ड को सम्मिलित करता है तो तालिका 1 जॉन यूएस 2 मार्क यूके 3 जॉन चीन 4 डेविड यूएस 5 जॉन चीन मुझे किस SQL ​​क्वेरी का उपयोग करना चाहिए? आईडी मान लेना ऑटो-वर्धित है, यह उस नाम और पता संयोजन के लिए सबसे अधिक मूल्य होगा। सेट पता personalinfo अद्यतन = 'अमेरिका' कहां आईडी = (चयन मैक्स (आईडी) personalinfo से जहां नाम = 'जॉन' और पता = 'ब्रिटेन')
Read more

Send innerHTML text in URL in JSP -

-
To send innerhtml text of a tag to the URL on the onclick event handler on the JSP page and how to value it in another JSP page get receive? Here is my code & lt; A href = "DocumentViewer.jsp" & gt; Hello & lt; / A & gt; I want to send hello to url. help? You should assume the URL onclick event and use it JSP page In request.getParameter () example code below & lt; A href = "DocumentViewer.jsp? Proces = something" & gt; Hello & lt; / A & gt; And get it in JSP in this way. string supporters = request.getParameter ("proces");
Read more