[Android] Chèn ảnh động *.gif trong Android

Tạo một ứng dụng Android và đặt tên là AnimationGif với Activity chính là MainActivity.
Tiếp theo, ta copy một hình ảnh có định dạng *.gif vào trong thư mục /assets. Ở đây mình sẽ sử dụng tập tin test.gif.

Cách 1: Sử dụng GifDecoderView

Để hiển thị được ảnh dạng *.gif, chúng ta sẽ sử dụng một custom view có tên là GifDecoderView, và cần một class để decode tập tin *.gif, có tên là GifDecoder.


GifDecoder.java

public class GifDecoder {
        /**
         * File read status: No errors.
         */
        public static final int STATUS_OK = 0;
        /**
         * File read status: Error decoding file (may be partially decoded)
         */
        public static final int STATUS_FORMAT_ERROR = 1;
        /**
         * File read status: Unable to open source.
         */
        public static final int STATUS_OPEN_ERROR = 2;
        /** max decoder pixel stack size */
        protected static final int MAX_STACK_SIZE = 4096;
        protected InputStream in;
        protected int status;
        protected int width; // full image width
        protected int height; // full image height
        protected boolean gctFlag; // global color table used
        protected int gctSize; // size of global color table
        protected int loopCount = 1; // iterations; 0 = repeat forever
        protected int[] gct; // global color table
        protected int[] lct; // local color table
        protected int[] act; // active color table
        protected int bgIndex; // background color index
        protected int bgColor; // background color
        protected int lastBgColor; // previous bg color
        protected int pixelAspect; // pixel aspect ratio
        protected boolean lctFlag; // local color table flag
        protected boolean interlace; // interlace flag
        protected int lctSize; // local color table size
        protected int ix, iy, iw, ih; // current image rectangle
        protected int lrx, lry, lrw, lrh;
        protected Bitmap image; // current frame
        protected Bitmap lastBitmap; // previous frame
        protected byte[] block = new byte[256]; // current data block
        protected int blockSize = 0; // block size last graphic control extension info
        protected int dispose = 0; // 0=no action; 1=leave in place; 2=restore to bg; 3=restore to prev
        protected int lastDispose = 0;
        protected boolean transparency = false; // use transparent color
        protected int delay = 0; // delay in milliseconds
        protected int transIndex; // transparent color index
        // LZW decoder working arrays
        protected short[] prefix;
        protected byte[] suffix;
        protected byte[] pixelStack;
        protected byte[] pixels;
        protected Vector<GifFrame> frames; // frames read from current file
        protected int frameCount;
 
        private static class GifFrame {
                public GifFrame(Bitmap im, int del) {
                        image = im;
                        delay = del;
                }
 
                public Bitmap image;
                public int delay;
        }
 
        /**
         * Gets display duration for specified frame.
         * 
         * @param n
         *          int index of frame
         * @return delay in milliseconds
         */
        public int getDelay(int n) {
                delay = -1;
                if ((n >= 0) && (n < frameCount)) {
                        delay = frames.elementAt(n).delay;
                }
                return delay;
        }
 
        /**
         * Gets the number of frames read from file.
         * 
         * @return frame count
         */
        public int getFrameCount() {
                return frameCount;
        }
 
        /**
         * Gets the first (or only) image read.
         * 
         * @return BufferedBitmap containing first frame, or null if none.
         */
        public Bitmap getBitmap() {
                return getFrame(0);
        }
 
        /**
         * Gets the "Netscape" iteration count, if any. A count of 0 means repeat indefinitiely.
         * 
         * @return iteration count if one was specified, else 1.
         */
        public int getLoopCount() {
                return loopCount;
        }
 
        /**
         * Creates new frame image from current data (and previous frames as specified by their disposition codes).
         */
        protected void setPixels() {
                // expose destination image's pixels as int array
                int[] dest = new int[width * height];
                // fill in starting image contents based on last image's dispose code
                if (lastDispose > 0) {
                        if (lastDispose == 3) {
                                // use image before last
                                int n = frameCount - 2;
                                if (n > 0) {
                                        lastBitmap = getFrame(n - 1);
                                } else {
                                        lastBitmap = null;
                                }
                        }
                        if (lastBitmap != null) {
                                lastBitmap.getPixels(dest, 0, width, 0, 0, width, height);
                                // copy pixels
                                if (lastDispose == 2) {
                                        // fill last image rect area with background color
                                        int c = 0;
                                        if (!transparency) {
                                                c = lastBgColor;
                                        }
                                        for (int i = 0; i < lrh; i++) {
                                                int n1 = (lry + i) * width + lrx;
                                                int n2 = n1 + lrw;
                                                for (int k = n1; k < n2; k++) {
                                                        dest[k] = c;
                                                }
                                        }
                                }
                        }
                }
                // copy each source line to the appropriate place in the destination
                int pass = 1;
                int inc = 8;
                int iline = 0;
                for (int i = 0; i < ih; i++) {
                        int line = i;
                        if (interlace) {
                                if (iline >= ih) {
                                        pass++;
                                        switch (pass) {
                                        case 2:
                                                iline = 4;
                                                break;
                                        case 3:
                                                iline = 2;
                                                inc = 4;
                                                break;
                                        case 4:
                                                iline = 1;
                                                inc = 2;
                                                break;
                                        default:
                                                break;
                                        }
                                }
                                line = iline;
                                iline += inc;
                        }
                        line += iy;
                        if (line < height) {
                                int k = line * width;
                                int dx = k + ix; // start of line in dest
                                int dlim = dx + iw; // end of dest line
                                if ((k + width) < dlim) {
                                        dlim = k + width; // past dest edge
                                }
                                int sx = i * iw; // start of line in source
                                while (dx < dlim) {
                                        // map color and insert in destination
                                        int index = ((int) pixels[sx++]) & 0xff;
                                        int c = act[index];
                                        if (c != 0) {
                                                dest[dx] = c;
                                        }
                                        dx++;
                                }
                        }
                }
                image = Bitmap.createBitmap(dest, width, height, Config.ARGB_4444);
        }
 
        /**
         * Gets the image contents of frame n.
         * 
         * @return BufferedBitmap representation of frame, or null if n is invalid.
         */
        public Bitmap getFrame(int n) {
                if (frameCount <= 0)
                        return null;
                n = n % frameCount;
                return ((GifFrame) frames.elementAt(n)).image;
        }
 
        /**
         * Reads GIF image from stream
         * 
         * @param is
         *          containing GIF file.
         * @return read status code (0 = no errors)
         */
        public int read(InputStream is) {
                init();
                if (is != null) {
                        in = is;
                        readHeader();
                        if (!err()) {
                                readContents();
                                if (frameCount < 0) {
                                        status = STATUS_FORMAT_ERROR;
                                }
                        }
                } else {
                        status = STATUS_OPEN_ERROR;
                }
                try {
                        is.close();
                } catch (Exception e) {
                }
                return status;
        }
 
        /**
         * Decodes LZW image data into pixel array. Adapted from John Cristy's BitmapMagick.
         */
        protected void decodeBitmapData() {
                int nullCode = -1;
                int npix = iw * ih;
                int available, clear, code_mask, code_size, end_of_information, in_code, old_code, bits, code, count, i, datum, data_size, first, top, bi, pi;
                if ((pixels == null) || (pixels.length < npix)) {
                        pixels = new byte[npix]; // allocate new pixel array
                }
                if (prefix == null) {
                        prefix = new short[MAX_STACK_SIZE];
                }
                if (suffix == null) {
                        suffix = new byte[MAX_STACK_SIZE];
                }
                if (pixelStack == null) {
                        pixelStack = new byte[MAX_STACK_SIZE + 1];
                }
                // Initialize GIF data stream decoder.
                data_size = read();
                clear = 1 << data_size;
                end_of_information = clear + 1;
                available = clear + 2;
                old_code = nullCode;
                code_size = data_size + 1;
                code_mask = (1 << code_size) - 1;
                for (code = 0; code < clear; code++) {
                        prefix[code] = 0; 
                        suffix[code] = (byte) code;
                }
                // Decode GIF pixel stream.
                datum = bits = count = first = top = pi = bi = 0;
                for (i = 0; i < npix;) {
                        if (top == 0) {
                                if (bits < code_size) {
                                        // Load bytes until there are enough bits for a code.
                                        if (count == 0) {
                                                // Read a new data block.
                                                count = readBlock();
                                                if (count <= 0) {
                                                        break;
                                                }
                                                bi = 0;
                                        }
                                        datum += (((int) block[bi]) & 0xff) << bits;
                                        bits += 8;
                                        bi++;
                                        count--;
                                        continue;
                                }
                                // Get the next code.
                                code = datum & code_mask;
                                datum >>= code_size;
                                bits -= code_size;
                                // Interpret the code
                                if ((code > available) || (code == end_of_information)) {
                                        break;
                                }
                                if (code == clear) {
                                        // Reset decoder.
                                        code_size = data_size + 1;
                                        code_mask = (1 << code_size) - 1;
                                        available = clear + 2;
                                        old_code = nullCode;
                                        continue;
                                }
                                if (old_code == nullCode) {
                                        pixelStack[top++] = suffix[code];
                                        old_code = code;
                                        first = code;
                                        continue;
                                }
                                in_code = code;
                                if (code == available) {
                                        pixelStack[top++] = (byte) first;
                                        code = old_code;
                                }
                                while (code > clear) {
                                        pixelStack[top++] = suffix[code];
                                        code = prefix[code];
                                }
                                first = ((int) suffix[code]) & 0xff;
                                // Add a new string to the string table,
                                if (available >= MAX_STACK_SIZE) {
                                        break;
                                }
                                pixelStack[top++] = (byte) first;
                                prefix[available] = (short) old_code;
                                suffix[available] = (byte) first;
                                available++;
                                if (((available & code_mask) == 0) && (available < MAX_STACK_SIZE)) {
                                        code_size++;
                                        code_mask += available;
                                }
                                old_code = in_code;
                        }
                        // Pop a pixel off the pixel stack.
                        top--;
                        pixels[pi++] = pixelStack[top];
                        i++;
                }
                for (i = pi; i < npix; i++) {
                        pixels[i] = 0; // clear missing pixels
                }
        }
 
        /**
         * Returns true if an error was encountered during reading/decoding
         */
        protected boolean err() {
                return status != STATUS_OK;
        }
 
        /**
         * Initializes or re-initializes reader
         */
        protected void init() {
                status = STATUS_OK;
                frameCount = 0;
                frames = new Vector<GifFrame>();
                gct = null;
                lct = null;
        }
 
        /**
         * Reads a single byte from the input stream.
         */
        protected int read() {
                int curByte = 0;
                try {
                        curByte = in.read();
                } catch (Exception e) {
                        status = STATUS_FORMAT_ERROR;
                }
                return curByte;
        }
 
        /**
         * Reads next variable length block from input.
         * 
         * @return number of bytes stored in "buffer"
         */
        protected int readBlock() {
                blockSize = read();
                int n = 0;
                if (blockSize > 0) {
                        try {
                                int count = 0;
                                while (n < blockSize) {
                                        count = in.read(block, n, blockSize - n);
                                        if (count == -1) {
                                                break;
                                        }
                                        n += count;
                                }
                        } catch (Exception e) {
                                e.printStackTrace();
                        }
                        if (n < blockSize) {
                                status = STATUS_FORMAT_ERROR;
                        }
                }
                return n;
        }
 
        /**
         * Reads color table as 256 RGB integer values
         * 
         * @param ncolors
         *          int number of colors to read
         * @return int array containing 256 colors (packed ARGB with full alpha)
         */
        protected int[] readColorTable(int ncolors) {
                int nbytes = 3 * ncolors;
                int[] tab = null;
                byte[] c = new byte[nbytes];
                int n = 0;
                try {
                        n = in.read(c);
                } catch (Exception e) {
                        e.printStackTrace();
                }
                if (n < nbytes) {
                        status = STATUS_FORMAT_ERROR;
                } else {
                        tab = new int[256]; // max size to avoid bounds checks
                        int i = 0;
                        int j = 0;
                        while (i < ncolors) {
                                int r = ((int) c[j++]) & 0xff;
                                int g = ((int) c[j++]) & 0xff;
                                int b = ((int) c[j++]) & 0xff;
                                tab[i++] = 0xff000000 | (r << 16) | (g << 8) | b;
                        }
                }
                return tab;
        }
 
        /**
         * Main file parser. Reads GIF content blocks.
         */
        protected void readContents() {
                // read GIF file content blocks
                boolean done = false;
                while (!(done || err())) {
                        int code = read();
                        switch (code) {
                        case 0x2C: // image separator
                                readBitmap();
                                break;
                        case 0x21: // extension
                                code = read();
                                switch (code) {
                                case 0xf9: // graphics control extension
                                        readGraphicControlExt();
                                        break;
                                case 0xff: // application extension
                                        readBlock();
                                        String app = "";
                                        for (int i = 0; i < 11; i++) {
                                                app += (char) block[i];
                                        }
                                        if (app.equals("NETSCAPE2.0")) {
                                                readNetscapeExt();
                                        } else {
                                                skip(); // don't care
                                        }
                                        break;
                                case 0xfe:// comment extension
                                        skip();
                                        break;
                                case 0x01:// plain text extension
                                        skip();
                                        break;
                                default: // uninteresting extension
                                        skip();
                                }
                                break;
                        case 0x3b: // terminator
                                done = true;
                                break;
                        case 0x00: // bad byte, but keep going and see what happens break;
                        default:
                                status = STATUS_FORMAT_ERROR;
                        }
                }
        }
 
        /**
         * Reads Graphics Control Extension values
         */
        protected void readGraphicControlExt() {
                read(); // block size
                int packed = read(); // packed fields
                dispose = (packed & 0x1c) >> 2; // disposal method
                if (dispose == 0) {
                        dispose = 1; // elect to keep old image if discretionary
                }
                transparency = (packed & 1) != 0;
                delay = readShort() * 10; // delay in milliseconds
                transIndex = read(); // transparent color index
                read(); // block terminator
        }
 
        /**
         * Reads GIF file header information.
         */
        protected void readHeader() {
                String id = "";
                for (int i = 0; i < 6; i++) {
                        id += (char) read();
                }
                if (!id.startsWith("GIF")) {
                        status = STATUS_FORMAT_ERROR;
                        return;
                }
                readLSD();
                if (gctFlag && !err()) {
                        gct = readColorTable(gctSize);
                        bgColor = gct[bgIndex];
                }
        }
 
        /**
         * Reads next frame image
         */
        protected void readBitmap() {
                ix = readShort(); // (sub)image position & size
                iy = readShort();
                iw = readShort();
                ih = readShort();
                int packed = read();
                lctFlag = (packed & 0x80) != 0; // 1 - local color table flag interlace
                lctSize = (int) Math.pow(2, (packed & 0x07) + 1);
                // 3 - sort flag
                // 4-5 - reserved lctSize = 2 << (packed & 7); // 6-8 - local color
                // table size
                interlace = (packed & 0x40) != 0;
                if (lctFlag) {
                        lct = readColorTable(lctSize); // read table
                        act = lct; // make local table active
                } else {
                        act = gct; // make global table active
                        if (bgIndex == transIndex) {
                                bgColor = 0;
                        }
                }
                int save = 0;
                if (transparency) {
                        save = act[transIndex];
                        act[transIndex] = 0; // set transparent color if specified
                }
                if (act == null) {
                        status = STATUS_FORMAT_ERROR; // no color table defined
                }
                if (err()) {
                        return;
                }
                decodeBitmapData(); // decode pixel data
                skip();
                if (err()) {
                        return;
                }
                frameCount++;
                // create new image to receive frame data
                image = Bitmap.createBitmap(width, height, Config.ARGB_4444);
                setPixels(); // transfer pixel data to image
                frames.addElement(new GifFrame(image, delay)); // add image to frame
                // list
                if (transparency) {
                        act[transIndex] = save;
                }
                resetFrame();
        }
 
        /**
         * Reads Logical Screen Descriptor
         */
        protected void readLSD() {
                // logical screen size
                width = readShort();
                height = readShort();
                // packed fields
                int packed = read();
                gctFlag = (packed & 0x80) != 0; // 1 : global color table flag
                // 2-4 : color resolution
                // 5 : gct sort flag
                gctSize = 2 << (packed & 7); // 6-8 : gct size
                bgIndex = read(); // background color index
                pixelAspect = read(); // pixel aspect ratio
        }
 
        /**
         * Reads Netscape extenstion to obtain iteration count
         */
        protected void readNetscapeExt() {
                do {
                        readBlock();
                        if (block[0] == 1) {
                                // loop count sub-block
                                int b1 = ((int) block[1]) & 0xff;
                                int b2 = ((int) block[2]) & 0xff;
                                loopCount = (b2 << 8) | b1;
                        }
                } while ((blockSize > 0) && !err());
        }
 
        /**
         * Reads next 16-bit value, LSB first
         */
        protected int readShort() {
                // read 16-bit value, LSB first
                return read() | (read() << 8);
        }
 
        /**
         * Resets frame state for reading next image.
         */
        protected void resetFrame() {
                lastDispose = dispose;
                lrx = ix;
                lry = iy;
                lrw = iw;
                lrh = ih;
                lastBitmap = image;
                lastBgColor = bgColor;
                dispose = 0;
                transparency = false;
                delay = 0;
                lct = null;
        }
 
        /**
         * Skips variable length blocks up to and including next zero length block.
         */
        protected void skip() {
                do {
                        readBlock();
                } while ((blockSize > 0) && !err());
        }
}

GifDecoderView.java

public class GifDecoderView extends ImageView {
 
	public GifDecoderView(Context context) {
		super(context);
	}
 
	public GifDecoderView(Context context, InputStream stream) {
		super(context);
		playGif(stream);
	}
 
	private boolean mIsPlayingGif = false;
 
	private GifDecoder mGifDecoder;
 
	private Bitmap mTmpBitmap;
 
	final Handler mHandler = new Handler();
 
	final Runnable mUpdateResults = new Runnable() {
		public void run() {
			if (mTmpBitmap != null && !mTmpBitmap.isRecycled()) {
				GifDecoderView.this.setImageBitmap(mTmpBitmap);
			}
		}
	};
 
	private void playGif(InputStream stream) {
		mGifDecoder = new GifDecoder();
		mGifDecoder.read(stream);
 
		mIsPlayingGif = true;
 
		new Thread(new Runnable() {
			public void run() {
				final int n = mGifDecoder.getFrameCount();
				final int ntimes = mGifDecoder.getLoopCount();
				int repetitionCounter = 0;
				do {
					for (int i = 0; i < n; i++) {
						mTmpBitmap = mGifDecoder.getFrame(i);
						int t = mGifDecoder.getDelay(i);
						mHandler.post(mUpdateResults);
						try {
							Thread.sleep(t);
						} catch (InterruptedException e) {
							e.printStackTrace();
						}
					}
					if (ntimes != 0) {
						repetitionCounter++;
					}
				} while (mIsPlayingGif && (repetitionCounter <= ntimes));
			}
		}).start();
	}
 
	public void stopRendering() {
		mIsPlayingGif = true;
	}
}

Tiếp theo, ta chỉnh sửa MainActivity để hiển thị tập tin test.gif.
Chúng ta đọc tập tin test.gif vào trong một InputStream

		InputStream stream = null;
		try {
			stream = getAssets().open(&quot;test.gif&quot;);
		} catch (IOException e) {
			e.printStackTrace();
		}

Sau đó khởi tạo một GifDecoderView với tham số là InputStream vừa có như sau

		GifDecoderView view = new GifDecoderView(this, stream);

Cuối cùng là gán nội dung vào view của Activity để hiển thị:

		setContentView(view);

Cách 2: Sử dụng GifWebView

Cách này, chúng ta sẽ sử dụng GifWebView. Thực tế, ở đây ta sử dụng WebView, chỉ là custom lại để hiển thị ảnh từ đường dẫn đưa vào.
Tạo một class GifWebView với nội dung sau.

public class GifWebView extends WebView {
 
	public GifWebView(Context context, String path) {
		super(context);
		loadUrl(path);
	}
}

Sau đó, chỉnh sửa lại MainActivity. Chúng ta chỉ cần một đoạn mã sau để hiển thị test.gif

		GifWebView view = new GifWebView(this,"file:///android_asset/test.gif");

Và gán view này để hiển thị trên thiết bị:

		setContentView(view);

PALINY – spoj

Đề bài:


Thuật toán:


Gợi ý 1
Gợi ý 2

Code:


{$H+}
uses math;
const
  fi='';//paliny.inp';
  fo='';//paliny.out';
  maxn=50003;
  pp=307;
  base=trunc(1e9)+7;
var
  i,j,n,d,c,g,top,ans : longint;
  ha,hb,pow : array[0..maxn] of int64;
  a : array[1..maxn] of longint;
  s : string;
function gethash1(l,r : longint) : int64;
  begin
    gethash1 := (ha[r] - ha[l-1] * pow[r-l+1] + base * base) mod base;
  end;
function gethash2(l,r : longint) : int64;
  begin
    gethash2 := (hb[r] - hb[l+1] * pow[l-r+1] + base * base) mod base;
  end;
function ok ( le : longint) : boolean;
  var i,j : longint;
  begin
    for i := 1 to n - le + 1 do
      if gethash1(i,i+le-1) = gethash2(i+le-1,i) then exit(true);
    exit(false);
  end;
procedure process;
  begin
  d := 1 ;
  c := top ;
  g := (d+c) div 2;
  while (G<>d) and (g<>C) do
    begin
      if ok (a[g]) then d := g else c := g;
      g := (d+c) div 2;
    end;
  for g := c downto d do
    if ok (a[g]) then
      begin
        ans := max(ans,a[g]);
        exit;
      end;
  end;
procedure push(x : longint);
  begin
    inc(top);
    a[top] := x;
  end;
begin
  assign(input,fi);reset(input);
  assign(output,fo);rewrite(output);
  readln(n);
  readln(s);
  pow[0] := 1;
  for i := 1 to n do pow[i] := pow[i-1] * pp mod base;
  for i := 1 to n do ha[i] := ( ha[i-1] * pp + ord(s[i]) ) mod base;
  for i := n downto 1 do hb[i] := ( hb[i+1] * pp + ord(s[i]) ) mod base;
  top := 0;
  for i := 1 to n do
    if i mod 2 = 0 then push(i);
  process;
  top := 0;
  for i := 1 to n do
    if i mod 2 = 1 then push(i);
  process;
  writeln(ans);
  close(input);close(output);
end.

Các kiểu dữ liệu trong C++

Có 4 kiểu dữ liệu cơ bản trong C++ là: char, int, float, double.

kieu-du-lieu-yeulaptrinh.pw

TT Kiểu dữ liệu Kích thước              Miền giá trị
(Type) (Length) (Range)
1 unsigned char 1 byte 0 đến 255
2 char 1 byte – 128 đến 127
3 enum 2 bytes – 32,768 đến 32,767
4 unsigned int 2 bytes 0 đến 65,535
5 short int 2 bytes – 32,768 đến 32,767
6 int 2 bytes – 32,768 đến 32,767
7 unsigned long 4 bytes 0 đến 4,294,967,295
8 long 4 bytes – 2,147,483,648 đến 2,147,483,647
9 float 4 bytes 3.4 * 10–38
đến 3.4 * 1038
10 double 8 bytes 1.7 * 10–308
đến 1.7 * 10308
11 long double 10 bytes 3.4 * 10–4932
đến 1.1 * 104932
Những bài viết có thể bạn thích:

Khái niệm về kiểu dữ liệu

Thông thường dữ liệu hay dùng là số và chữ. Tuy nhiên việc phân chia chỉ 2 loai dữ liệu là không đủ. Để dễ dàng hơn cho lập trình, hầu hết các NNLT đều phân chia dữ liệu thành nhiều kiểu khác nhau được gọi là các kiểu cơ bản hay chuẩn. Trên cơ sở kết hợp các kiểu dữ liệu chuẩn, NSD có thể tự đặt ra các kiểu dữ liệu mới để phục vụ cho chương trình giải quyết bài toán của mình. Có nghĩa lúc đó mỗi đối tượng được quản lý trong chương trình sẽ là một tập hợp nhiều thông tin hơn và được tạo thành từ nhiều loại (kiểu) dữ liệu khác nhau. Dưới đây chúng ta sẽ xét đến một số kiểu dữ liệu chuẩn được qui định sẵn bởi C++.

Một biến như  đã biết là một số ô nhớ liên tiếp nào đó trong bộ nhớ dùng để lưu  trữ dữ liệu (vào, ra hay kết quả trung gian) trong quá trình hoạt động của chương trình. Để quản lý chặt chẽ các biến, NSD cần khai báo cho chương trình biết trước tên biến  và kiểu của dữ liệu được chứa trong biến. Việc khai báo này sẽ làm chương trình quản lý các biến dễ dàng hơn như trong việc phân bố bộ nhớ cũng như quản lý các tính toán trên biến theo nguyên tắc: chỉ có các dữ liệu cùng kiểu với nhau mới được phép làm toán với nhau. Do đó, khi đề cập đến một kiểu chuẩn của một NNLT, thông thường chúng ta sẽ xét đến các yếu tố sau:

  • tên kiểu: là một từ dành riêng để chỉ định kiểu của dữ liệu.
  • số byte trong bộ nhớ để lưu trữ một đơn vị dữ liệu thuộc kiểu này: Thông thường số byte này phụ thuộc vào các trình biên dịch và hệ thống máy khác nhau, ở đây ta chỉ xét đến hệ thống máy PC thông dụng hiện
  • Miền giá trị của kiểu: Cho biết một đơn vị dữ liệu thuộc kiểu này sẽ có thể lấy giá trị trong miền nào, ví dụ nhỏ nhất và lớn nhất là bao nhiêu. Hiển nhiên các giá trị này phụ thuộc vào số byte mà hệ thống máy qui định cho từng kiểu. NSD cần nhớ đến miền giá trị này để khai báo kiểu cho các biến cần sử dụng một cách thích hợp.

Dưới đây là bảng tóm tắt một số kiểu chuẩn đơn giản và các thông số của nó được sử dụng trong C++.

Loại dữ liệu Tên kiểu Số ô nhớ Miền giá trị
Kí tự char 1 byte – 128 .. 127
unsigned char 1 byte 0 .. 255
Số nguyên int 2 byte – 32768 .. 32767
unsigned int 2 byte 0 .. 65535
short long 2 byte

4 byte

– 32768 .. 32767

– 215 .. 215  – 1

Số thực float 4 byte ± 10 -37  . . ± 10 +38
double 8 byte ± 10 -307  . . ± 10 +308

Bảng 1. Các loại kiểu đơn giản

Trong chương này chúng ta chỉ xét các loại kiểu đơn giản trên đây. Các loại kiểu có cấu trúc do người dùng định nghĩa sẽ được trình bày trong các chương sau.

Kiểu ký tự

Một kí tự là một kí hiệu trong bảng mã ASCII. Như đã biết một số kí tự có mặt chữ trên bàn phím (ví dụ các chữ cái, chữ số) trong khi một số kí tự lại không (ví dụ kí tự biểu diễn việc lùi lại một ô trong văn bản, kí tự chỉ việc kết thúc một dòng hay kết thúc một văn bản). Do vậy để biểu diễn một kí tự người ta dùng chính mã ASCII của kí tự đó trong bảng mã ASCII và thường gọi là giá trị của kí tự. Ví dụ phát biểu “Cho kí  tự ‘A'” là cũng tương đương với phát biểu “Cho kí tự 65” (65 là mã ASCII của kí tự ‘A’), hoặc “Xoá kí tự xuống dòng” là cũng tương đương với phát biểu “Xoá kí tự 13” vì 13 là mã ASCII của kí tự xuống dòng.

Như vậy một biến kiểu kí tự có thể được nhận giá trị theo 2 cách tương đương – chữ hoặc giá trị số: ví dụ giả sử c là một biến kí tự thì câu lệnh gán c = ‘A’ cũng tương đương với câu lệnh gán c = 65. Tuy nhiên để sử dụng giá trị số của một kí tự c nào đó  ta phải yêu cầu đổi c sang giá trị số bằng câu lệnh int(c).

Theo bảng trên ta thấy có  2 loại kí tự là char với miền giá trị từ -128 đến   127 và unsigned char (kí tự không dấu) với miền giá trị từ 0 đến 255. Trường hợp một biến được gán giá trị vượt ra ngoài miền giá trị của kiểu thì giá trị của biến sẽ được tính theo mã bù – (256 – c). Ví dụ nếu gán cho char c giá trị 179 (vượt khỏi miền giá trị đã được qui định của char) thì giá trị thực sự được lưu trong máy sẽ là – (256 – 179) = -77.

Ví dụ 1 :

char c, d ;                                       // c, d được phép gán giá trị từ -128 đến 127

unsigned e ;                                   // e được phép gán giá trị từ 0 đến 255

c = 65 ; d = 179 ;                           // d có giá trị ngoài miền cho phép

e = 179; f = 330 ;                           // f có giá trị ngoài miền cho phép

cout << c << int(c) ;                                        // in ra chữ cái ‘A’ và giá trị số 65

cout << d << int(d) ;                                        // in ra là kí tự ‘|’ và giá trị số -77

cout << e << int(e)                                          // in ra là kí tự ‘|’ và giá trị số 179

cout << f << int(f)                          // in ra là kí tự ‘J’ và giá trị số 74

Chú ý: Qua ví dụ trên ta thấy một biến nếu được gán giá trị ngoài miền cho phép sẽ dẫn đến kết quả không theo suy nghĩ thông thường. Do vậy nên tuân thủ qui tắc chỉ gán giá trị cho biến thuộc miền giá trị mà kiểu của biến đó qui định. Ví dụ nếu muốn sử dụng biến có giá trị từ 128 .. 255 ta nên khai báo biến dưới dạng kí tự không dấu (unsigned char), còn nếu giá trị vượt quá 255 ta nên chuyển sang kiểu nguyên (int) chẳng hạn.

Kiểu số nguyên

Các số nguyên được phân chia thành 4 loại kiểu khác nhau với các miền giá trị tương ứng được cho trong bảng 1. Đó là kiểu số nguyên ngắn (short) tương đương với kiểu số nguyên (int) sử dụng 2 byte và số nguyên dài (long int) sử dụng 4 byte. Kiểu số nguyên thường được chia làm 2 loại có dấu (int) và không dấu (unsigned int hoặc có thể viết gọn hơn là unsigned). Qui tắc mã bù cũng được áp dụng nếu giá trị của biến vượt ra ngoài miền giá trị cho phép, vì vậy cần cân nhắc khi khai báo kiểu cho các  biến. Ta thường sử dụng kiểu int cho các số nguyên trong các bài toán với miền giá trị vừa phải (có giá trị tuyệt đối bé hơn 32767), chẳng hạn các biến đếm trong các vòng lặp, …

Kiểu số thực

Để sử dụng số thực ta cần khai báo kiểu float hoặc double mà miền giá trị của chúng được cho trong bảng 1. Các giá trị số kiểu double được gọi là số thực với độ chính xác gấp đôi vì với kiểu dữ liệu này máy tính có cách biểu diễn khác so với kiểu float để đảm bảo số số lẻ sau một số thực có thể tăng lên đảm bảo tính chính xác cao hơn so với số kiểu float. Tuy nhiên, trong các bài toán thông dụng thường ngày độ chính xác của số kiểu float là đủ dùng.

Như đã nhắc đến trong phần các lệnh vào/ra ở chương 1, liên quan đến việc in ấn số thực ta có một vài cách thiết đặt dạng in theo ý muốn, ví dụ độ rộng tối thiểu để in một số hay số số lẻ thập phân cần in …

Ví dụ 2 : Chương trình sau đây sẽ in diện tích và chu vi của một hình tròn có bán kính 2cm với 3 số lẻ.

#include <iostream.h>

#include <iomanip.h> void main()

{

float r = 2 ;                            // r là tên biến dùng để chứa bán kính

cout << “Diện tích = ” << setiosflags(ios::showpoint) ;

cout << setprecision(3) << r * r * 3.1416 ; getch() ;

}

 

QBPOINT – SPOJ

Đề bài: http://vn.spoj.com/problems/QBPOINT/

Thuật toán:

  • Duyệt n điểm, với mỗi điểm i ta:
    • Duyệt các điểm j <> i rồi tính vector ij lưu lại vào 1 mảng ss[]
    • Sort lại mảng ss[]
    • 3 điểm i,j,k thẳng hàng nếu vector ij = vector ik

Code:

#include <bits/stdc++.h>
#define FORE(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define FOR(i, a, b) for(int i = a; i < b; i++)
const int MAXN = 1e5 * 5;
const int INF = 1e9 + 7;
 
using namespace std;
int n,x[2001],y[2001];
long long res;
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("tripoint.inp", "r", stdin);
    freopen("tripoint.out", "w", stdout);
    #endif //
    cin>>n;
    FORE(i,1,n) cin>>x[i]>>y[i];
    FORE(i,1,n)
    {
        vector <double> ss; int cc=0;
        FORE(j,1,n)
        if (x[j]!=x[i])
            ss.push_back((double) (y[j]-y[i])/(x[j]-x[i]));
        else ++cc;
        sort(ss.begin(),ss.end());
        int sl=(cc-2)*(cc-1);
        if (ss.size())
        {
            int dem=1;
            FORE(j,1,ss.size()-1)
            if (ss[j]==ss[j-1]) ++dem;
            else
            {
                sl+=dem*(dem-1);
                dem=1;
            }
            sl+=dem*(dem-1);
        }
        res+=sl;
    }
    cout<<res/6;
    return 0;
}

SUBSTR – spoj

Đề bài:

Thuật toán:

  • (đang cập nhập)

Code:

const
  fi='';
  fo='';
  maxn=trunc(1e6);
  base=trunc(1e9)+7;
  pp=307;
var
  f : array[0..maxn] of int64;
  i,j,n,m : longint;
  hb : int64;
  a,b : array[1..maxn] of byte;
  ha,pow : array[0..maxn] of int64;
procedure enter;
var x : ansistring;
begin
  assign(input,fi);reset(input);
  readln(x);
  m := length(x);
  for i := 1 to m do a[i] := ord(x[i])-48;
  readln(x);
  n := length(x);
  for i := 1 to n do b[i] := ord(x[i])-48;
  close(input);
end;
function gethash(l,r : longint) : int64;
begin
  gethash := (ha[r]-ha[l-1]*pow[r-l+1] + base*base) mod base;
end;
procedure process;
begin
  assign(output,fo);rewrite(output);
  ha[0] := 0;
  for i:=1 to m do ha[i] := (ha[i-1]*pp + a[i]) mod base;
  pow[0] := 1;
  for i:=1 to m do pow[i] := pow[i-1]*pp mod base;
  hb := 0;
  for i:=1 to n do hb := (hb*pp + b[i]) mod base;
  for i:=1 to m-n+1 do
    if hb = gethash(i,i+n-1) then
      write(i,' ');
  close(output);
end;
begin
  enter;
  process;
end.

Thuật toán duyệt phân tập

Bài toán cơ bản:

Cho mảng A[1..n] đếm số dãy con của mảng có tổng bằng S với n<=40.

  • Inp: n, S, mảng A.
  • Out: kết quả bài toán.

Inp:

4 4

1 2 3 4

Out:

2

Các dãy con: (4) , (1,3)

Phân tích: 

  • Thuật toán ta nghĩ ra ngay là duyệt dãy nhị phân 01
  • Nhưng duyệt chỉ giải quyết được với n <= 20. Chính vì vậy phải dùng thuật toán duyệt phân tập mới có thể ăn full test 🙂

Tư tưởng thuật toán duyệt phân tập:

  • Chia mảng A làm 2 mảng nhỏ độ dài n/2
  • Khi đó max(n/2)=20 => duyệt
  • Khi duyệt các mảng nhỏ ta lưu tổng các dãy con của mảng nhỏ vào các mảng riêng S1[] và S2[]
  • Với mỗi giá trị S1[] ta tìm kiếm nhị phần trong S2[] phần tử có giá trị S-S1[i] (cộng res với số gt S-S1[i] trong S2[]
  • res là kết quả bài toán

Các bài tập luyện tập thêm:

COIN34 – SPOJ

VECTOR – spoj

DTTUI1 – spoj

CREC01 – SPOJ

Đề bài:

Thuật toán:

  • Bài này ta sử dụng kỹ thuật deque. Thuật toán cũng không có gì phức tạp. Bạn có thể đọc code bên dưới để hiểu thêm

Code:

Pascal : https://ideone.com/swTkml

const   fi      ='';
        fo      ='';
        oo      =1000;
 
var     a       :array[0..oo,0..oo] of 0..1;
        l,h,dem:array[0..oo+1] of int64;
        m, n    :longint;
 
procedure Optimize;
var     i, j    :longint;
        ans     :int64;
begin
        fillchar(h, sizeof(h),0);
        ans:=0;
        for i:=1 to m do
                begin
                        for j:=1 to n do
                                begin
                                        if a[i,j]=1 then begin
                                        l[j]:=j;
                                        h[j]:=h[j]+1;
                                        while h[l[j]-1]>h[j] do
                                                l[j]:=l[l[j]-1];
                                        dem[j]:=h[j]*(j-l[j]+1)+dem[l[j]-1];
                                        ans:=ans+dem[j];
                                        //writeln(ans,'==');
                                        //if (i=3) and (j=2) then writeln(dem[1]);
                                        end
                                        else begin
                                                dem[j]:=0;
                                                l[j]:=0;
                                                h[j]:=0;
                                        end;
 
                                end;
 
                end;
        writeln(ans);
end;
 
procedure run;
var     i, j, tg    :longint;
        s       :ansistring;
begin
        assign(input,fi);assign(output,fo);
        reset(input);rewrite(output);
        readln(m, n);
        for i:=1 to m do
                begin
                        readln(s);
                        for j:=1 to n do
                                        val(s[j],a[i,j]);
                end;
        Optimize;
        close(input);close(output);
 
end;
 
begin
        run;
end.

C++ : https://ideone.com/S0t4zZ

using namespace std;
#include<bits/stdc++.h>
 
#define BG begin()
#define ED end()
#define st first
#define nd second
#define PB push_back
#define PF push_front
#define FOR(i,a,b) for (long long i=a;i<b;i++)
#define FORE(i,a,b) for (long long i=a;i<=b;i++)
#define FORD(i,a,b) for (long long i=a;i>=b; i--)
#define ri(n)({\
    int neg=0;\
    n=0;\
    char ch;\
    for(ch=getchar(); ch<'0' || ch>'9'; ch=getchar()) if (ch=='-') neg=1-neg;\
    n=ch-48;\
    for(ch=getchar(); ch>='0' && ch<='9'; ch=getchar()) n=(n<<3)+(n<<1)+ch-48;\
    if (neg) n=-n;\
})
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> II;
typedef pair<ll,ll> LL;
const ll INF=1000000000+7;
const double esp=1e-13;
const double pi=3.141592653589;
 
 
ll m, n, a[1001][1001], H[1001], dem[1001], L[1001];
 
int main()
{
    //freopen("CREC01.inp", "r", stdin);
    //freopen("CREC01.out", "w", stdout);
    cin>>m>>n;
    char ch;
    FORE(i, 1, m)
        FORE(j, 1, n) {
            cin>>ch;
            a[i][j] = ch - '0';
        }
    memset(H, 0, sizeof(H));
    memset(L, 0, sizeof(L));
    memset(dem, 0, sizeof(dem));
    long long ans = 0;
    FORE(i, 1, m)
        FORE(j, 1, n) {
            //cout<<i<<" "<<j<<" "<<a[i][j]<<endl;
            if (a[i][j] == 1) {
                H[j]++;
                int k = j;
                while ( (k > 1) && (a[i][k-1] == 1) && (H[ k - 1 ] >= H[j]) ) k = L[k - 1];
                L[j] = k;
                dem[j] = H[j]*(j - L[j] + 1) + dem[L[j] - 1];
                ans += dem[j];
                //cout<<i<<"=="<<j<<"=="<<"=="<<H[j]<<"=="<<ans<<endl;
            }
            else
            {
                H[j] = 0;
                dem[j]= 0;
                L[j] = 0;
            }
        }
    cout<<ans;
}