How does this program work?
The important bit is where the wildcard is :
test*
te*ing
*ing
In the first case, with the wildcard at the end, testing and test*
:
def samePattern(main,pattern):
if pattern=="*" or main==pattern: # 3.
return True
if main=="": # 4.
return False
if main[0:1]==pattern[0:1]: # 1.
return samePattern(main[1:],pattern[1:]) #
if pattern[0:1]=="*":
return samePattern(main[1:],pattern) or samePattern(main,pattern[1:])
^ ^
| # 2. | # 5.
return False
Section 1. walks along both text and pattern for test
until the pattern gets to the wildcard and they aren't the same character anymore.
Section 2. triggers, and shifts only the text along one character and tries again.
Section 3. hits, the pattern is a single '*' with nothing else, and it returns True.
Section 2. comes back out with the True value, Python's short-circuit evaluation doesn't test the other side of the or
because it doesn't need to, and the whole thing collapses to True
successful match.
The second case, with the wildcard in the middle starts off the same way. testing and te*ing
:
Section 1. walks both text and pattern, until the pattern gets to the wildcard.
Now the text and pattern are sting and *ing
, which is the same as the third case - wildcard at the front.
The third case with the wildcard at the front, e.g. testing and *ing
:
Section 2. triggers because the pattern starts with a *. (It skips section 3. because it's not only a star). Section 2 moves one text character and tries again with the same pattern.
The same happens over and over until Section 4. triggers and the text has run out. Now this returns False.
Now the first False has come back from the left part of the or
test, the right part is tried for the first time. This shifts the pattern past the wildcard, *ing
becomes ing
.
But we're still deep in the recursion, at the last character of the text - g and ing
, which returns False from Section 1.
Both sides of the or
test at this depth returned False so the whole line does.
This comes back up a level, and the other side of that level's or
test is tried. ng and ing
. False from Section 1.
Both sides of the or
test at this depth returned False so the whole line does.
This comes back up a level, and the other side of that level's or
test is tried. ing and ing
. True from Section 3 and main==pattern
.
This returns True, the or
returns True and the whole thing collapses in a pile of Truth.
All the parts work together, but roughly speaking Section 1. matches text with text, Sections 2 and 3 match ending wildcards, and Sections 4 and 5 match beginning wildcards, and they overlap which takes care of wildcards-in-the-middle.
Adding some printf debugging helped me see what was going on:
first
def samePattern(main,pattern):
print "main", main, "pattern", pattern
[..]
then
if pattern[0:1]=="*":
x = samePattern(main[1:],pattern)
print "x", x
return x or samePattern(main,pattern[1:])
How does this program work?
That's because %d
expects an int
but you've provided a float.
Use %e
/%f
/%g
to print the float.
On why 0 is printed: The floating point number is converted to double
before sending to printf
. The number 1234.5 in double representation in little endian is
00 00 00 00 00 4A 93 40
A %d
consumes a 32-bit integer, so a zero is printed. (As a test, you could printf("%d, %d\n", 1234.5f);
You could get on output 0, 1083394560
.)
As for why the float
is converted to double
, as the prototype of printf is int printf(const char*, ...)
, from 6.5.2.2/7,
The ellipsis notation in a function prototype declarator causes argument type conversion to stop after the last declared parameter. The default argument promotions are performed on trailing arguments.
and from 6.5.2.2/6,
If the expression that denotes the called function has a type that does not include a prototype, the integer promotions are performed on each argument, and arguments that have type
float
are promoted todouble
. These are called the default argument promotions.
(Thanks Alok for finding this out.)
Why does this program work?
Console input (via the cin
std::istream
object) in most systems is line buffered. So when you call cin::operator>>
for a single character, the function does not in fact return until you press newline (because the underlying I/O system does not make data available to cin
until then). Any data entered up-to and including the <newline>
will be buffered and subsequent calls to cin::operator>>
will be serviced from the buffer until it is exhausted.
In this case cin >> buffer
, where buffer
is of type char
will indeed get a single character, but before that the console buffered an entire line and will use it to satisfy subsequent console input operations.
If you step through your code in your debugger the operation may be clearer to you.
How does this program work? How's firstGreaterEqual method working
So it is basically working on the principle of binary search like you pointed out.
Here is the algorithm break down in simple terms
- First you find the first occurence of the target that you are looking for
- If there is no occurence of the target, return [-1, -1]
Then find the first occurence of
target+1
, suppose that occurence is stored in variableend
, then the last occurence of the originaltarget
will be `end -1First you find the first occurence of the target that you are looking
Example arraynums = [5,7,7,8,8,10], target = 8
lo = 0
,hi = len(nums)
,mid = (hi+lo)//2
- Now you search the middle of the array, here
mid = 3
- The element at nums[3] is 8, which is the same as taget
- This is the starting index, return it and store in the value
start
Now since we got the first occurence we proceed to the next phase
Then find the first occurence of target+1
lo = 0
,hi = len(nums)
,mid = (hi+lo)//2
,target+1 = 9
- Now you search the middle of the array, here
mid = 3
- The element at nums[3] is 8, which is less than
target+1
, so we setlow = mid +1
- Next we set
mid = (hi+lo)//2
, which is 5 - The element at nums[5] is 10, which is more than
target+1
, so we sethi = mid
- After the previous step, we get out of
while loop
since the conditionwhile lo<hi
evaluates to False - REturn
lo
as the ending index
Now we have start = 3, and end = 5, so we return [start, end-1], i.e. [3,4]
Reference:
- GeeksForGeeks blog post for same problem
How does this litle program work?
You need to familiarize yourself with bitfields.
By default int has size of 32 bits(4 bytes). But using the given notation, you can specify how many bits are used for the variable.
So when you increment the value from 1, it overflows and returns to zero.
How is this program meant to work?
You would run it and use ctrl + d
to signal the EOF (end of file) when reading from the command line.
If you were reading a stream of bytes from a file then it would have that in there automatically. However, since you are reading from the command line, one needs to signal the end of file manually by using the key sequence above.
How it actually works
EOF usually represents -1 in (glibc at least) which is why you can't just say while(c) { do work; }
because any non-zero value is true -- hence EOF is true, just like any other positive number character returned by the call to getchar()
. This is why you have to directly check to see if c matches EOF (-1) with the code c != EOF
which appears in the stream when you send the EOF signal with ctrl + d
.
How does a program written in C++ work?
So how does windows run a program like that without any run time
environment for C++?
The premise of the question is actually not true. At least on Windows, there is in fact a runtime environment for C++. One component of this runtime (probably the most important one) is called the C Runtime, or the CRT. :-)
Typically before your program even enters the main()
function, the CRT performs a bunch of initialization routines, and when you return from the main()
function it cleans up after itself. The whole point of this dance is to provide standard functionality that virtually all C and C++ programs require.
If you've ever run across an error involving a missing msvcrt.dll
or anything like that (e.g. msvcr110.dll
for newer programs) when starting a Windows program, the lack of the CRT is what the program is complaining about. The msvcrt.dll
is the file that implements the CRT. It stands for "Microsoft Visual C Runtime".
Obviously, msvcrt.dll
and its relatives ship with the Windows operating system, which is why you don't typically run into problems with a missing runtime environment unlike the JRE, which must be installed by either the user or by the manufacturer of the computer.
However, Windows C++ applications are compiled to use a specific version of the MSVCRT, and if you have the wrong version of the MSVCRT, then the operating system will complain the same way as though it was missing.* What installers typically do is to check that the OS has the correct version, and if it doesn't it copies it somewhere on your computer from its own installation files.
The MSVCRT is however not a necessary nor sufficient condition for all Windows programs to work. It's entirely possible to write a program that is not dependent on the MSVCRT, and also entirely possible that a Windows program will have dependencies other than the MSVCRT. Virtually all nontrivial Windows programs will depend on the MSVCRT and other operating system components. The installer of the program would check for these as well.
There are some important differences between the JRE and the MSVCRT. One big difference is that the JRE implements a virtual machine environment for Java applications (that's how it achieves it's "cross-platform" capabilities) which may involve just-in-time compilation, etc. while the MSVCRT only provides standard functions and does nothing about the assembly code of your C++ programs.
*This is not strictly correct as C++ applications can statically link to the MSVCRT, which doesn't depend on the DLL. However, most Windows C++ applications dynamically link to it, in which case the correct DLL is required.
Related Topics
Utilizing C++ in iOS and MAC Os X Applications
Vc++ Fatal Error Lnk1168: Cannot Open Filename.Exe for Writing
Why Isn't There an Operator[] for a Std::List
How to Take Screenshot in Opengl
Initializing Container of Unique_Ptrs from Initializer List Fails with Gcc 4.7
How to Cast Simple Pointer to a Multidimensional-Array of Fixed Size
Brace Elision in Std::Array Initialization
Why Are '&Array' and 'Array' Pointing to the Same Address
Gcc -Wuninitialized/-Wmaybe-Uninitialized Issues
List of C++ Name Resolution (And Overloading) Rules
Are Global Variables in C++ Stored on the Stack, Heap or Neither of Them
How to Use Const in Vectors to Allow Adding Elements, But Not Modifications to the Already Added